Submission #2085631

---

Source Code Expand

//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#include <bits/stdc++.h>
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int LL
#define zero 0LL
using namespace std;
template<typename T> inline void maximize(T &a,T b){a=max(a,b);}
template<typename T> inline void minimize(T &a,T b){a=min(a,b);}
template<typename T> inline bool middle(T a,T b,T c){return b<=a && a<=c;}
typedef long long int;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
inline void outputVI(VI x){REP(i,SI(x)){cout << three(i," ","") << x[i];}OUT("");}
inline void outputVpr(Vpr x){REP(i,SI(x)){cout << three(i," ","") << x[i].second;}OUT("");}
const int SIZE1=5*1e5+1000;
const int SIZE2=5010;
const int SIZE3=55;
const int SIZE=SIZE1;
const LL p=7+1e9;
const LL INF=1LL<<60;
const long double EPS=1e-7;
string s;
ut N,M,K,X,L,Y,H,W,T;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE],nums[SIZE],maps[SIZE2][SIZE2],answer=zero;
 
////////////////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////////////////////////////////////////////////////////
int dy[]={0,1,0,-1},dx[]={1,0,-1,0};
char dc[]={'R','D','L','U'};
LL row[101][SIZE3][SIZE3];
LL st[101][2];
LL commands[2500];
bool getted[SIZE3][SIZE3];
std::chrono::system_clock::time_point start;
const int timelimit=3500;
inline int rnd(int T){
	//return ranger(mt);
	return rand()%T;
}
void timestart(){
	start=std::chrono::system_clock::now();
}
inline int nowtime(){
	return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now()-start).count();
}
LL calc(LL x,const VI& v){
	int nowy=st[x][0],nowx=st[x][1];
	REP(i,H) REP(j,W) getted[i][j]=false;
	int ans=0;
	REP(i,SI(v)){
	//	OUT2(nowy,nowx);
		if(row[x][nowy+dy[v[i]]][nowx+dx[v[i]]]<=1){
			nowy+=dy[v[i]];
			nowx+=dx[v[i]];
			if(!getted[nowy][nowx] && row[x][nowy][nowx]==0){
				ans++;
				getted[nowy][nowx]=1;
			}
		}
		if(row[x][nowy][nowx]==1) return ans;
	}
	return ans;
}
LL calcall(const VI& v){
	VI results;
	REP(i,N){
		results.PB(calc(i,v));
	}
	sort(ALL(results),greater<LL>());
	int ans=0;
	REP(i,K) ans+=results[i];
	return ans;
}
LL output(const VI& v){
	Vpr results;
	REP(i,N){
		results.PB(pr(calc(i,v),i));
		//DEBUG2(results.back().first,results.back().second);
	}
	sort(ALL(results),greater<pr>());
	VI anses;
	REP(i,K){
		anses.PB(results[i].second);
	}
	outputVI(anses);
	REP(i,SI(v)) cout << dc[v[i]];
	cout << endl;
}
LL solve(){
 	cin >> N >> K >> H >> W >>T;
 	char t;
 	REP(k,N)
 		REP(i,H){
 			string s;
 			cin >> s;
 			REP(j,W)
 				if(s[j]=='o') row[k][i][j]=0;
 				else if(s[j]=='x')row[k][i][j]=1;
 				else if(s[j]=='#')row[k][i][j]=2;
 				else if(s[j]=='@'){
 					row[k][i][j]=-1;
 					st[k][0]=i;
 					st[k][1]=j;
 				}
 		}
 	VI v;
 	int now1=0;
 	int now2=0;
 	REP(i,N){
 		if(i%2==0){
 			REP(j,i) v.PB(0);
 			REP(j,i) v.PB(1); 
 		}
 		else{
 			REP(j,i) v.PB(2);
 			REP(j,i) v.PB(3);
 		}
 		if(SI(v)>=T) break;
 	}
 	while(SI(v)>T) v.pop_back();
 	int times=0;
 	int nowscore=calcall(v);
 	while(true){
 		times++;
 		if(times==100){
 			if(nowtime()>timelimit) break;
 			else times=0;
 		}
 		//OUT(nowtime());
 		int xx=rnd(T),tmp=v[xx];
 		
 		v[xx]=rnd(4);
 		int score=calcall(v);
 		if(nowscore>score) v[xx]=tmp;
 	}
 	//DEBUG(calcall);
 	output(v);
	return 0;
}
signed main(){
	timestart();
	solve();
	return 0;
}

Submission Info

Judge Result