Submission #1017264
Source Code Expand
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
//const int INF=5e8;
int n;
int ar[4][305];
void ng(){
puts("NO");
exit(0);
}
int buf[305][305];//0:horizonal 1:vertical
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
//down,right,up,left
int LR[305],UD[305];
int ud[305],perm[305];
bool done[305][305];
bool vis[305][305];
bool start[305][305];
vector<pi> ever;
bool dfs(int y,int x){
dump(y);dump(x);
if(vis[y][x]){
prl;
int m=ever.size();
for(int i=m-1;i>=0;--i) if(ever[i]==mp(y,x)){
dump(ever[i]);
for(int j=m-1;j>i;--j){
dump(ever[j]);
int nxt=j+1;
if(nxt==m) nxt=i;
pi p=ever[j],q=ever[nxt];
swap(buf[p.fr][p.sc],buf[q.fr][q.sc]);
}
start[y][x]=1;
break;
}
vis[y][x]=0;
return true;
}
ever.pb(mp(y,x));
vis[y][x]=1;
int d=buf[y][x];
int py=y+dy[d],px=x+dx[d];
while(!(px<0 || py<0 || px>=n || py>=n)){
if(!done[py][px]){
if(dfs(py,px)){
if(start[y][x]){
start[y][x]=false;
ever.pop_back();
vis[y][x]=0;
return dfs(y,x);
}else{
vis[y][x]=0;
ever.pop_back();
return true;
}
}
}
px+=dx[d],py+=dy[d];
}
done[y][x]=1;
char code[]="DRUL";
printf("%c%d\n",code[buf[y][x]],buf[y][x]&1?y+1:x+1);
ever.pop_back();
return false;
}
int main(){
cin>>n;
REP(i,4) REP(j,n) cin>>ar[i][j];
REP(i,n) if(ar[0][i]+ar[1][i]>n || ar[2][i]+ar[3][i]>n) ng();
prl;
REP(i,n){
LR[i]=ar[2][i]+ar[3][i];
UD[i]=ar[0][i]+ar[1][i];
}
REP(j,n) ud[j]=UD[j];
REP(i,n){
REP(j,n) perm[j]=j;
sort(perm,perm+n,[&](int a,int b){
return ud[a]<ud[b];
});
REP(j,n){
if(j<LR[i]) buf[i][perm[j]]=0;
else buf[i][perm[j]]=1,--ud[perm[j]];
}
}
debug(ud,ud+n);
REP(i,n) if(ud[i]!=0) ng();
prl;
REP(i,n){
REP(j,n){
if(buf[i][j]==0){
if(ar[2][i]>0) buf[i][j]=3,--ar[2][i];
else buf[i][j]=1;
}else{
if(ar[0][j]>0) buf[i][j]=2,--ar[0][j];
else buf[i][j]=0;
}
}
}
REP(i,n) debug(buf[i],buf[i]+n);
REP(i,n) REP(j,n) if(!done[i][j]) dfs(i,j);
REP(i,n) debug(buf[i],buf[i]+n);
return 0;
}
Submission Info
Submission Time |
|
Task |
J - Neue Spiel |
User |
hogloid |
Language |
C++14 (GCC 5.4.1) |
Score |
2100 |
Code Size |
3244 Byte |
Status |
AC |
Exec Time |
137 ms |
Memory |
1664 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
2000 / 2000 |
100 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
3 ms |
256 KB |
01-02.txt |
AC |
3 ms |
256 KB |
01-03.txt |
AC |
3 ms |
256 KB |
01-04.txt |
AC |
3 ms |
256 KB |
01-05.txt |
AC |
3 ms |
256 KB |
01-06.txt |
AC |
3 ms |
384 KB |
01-07.txt |
AC |
3 ms |
384 KB |
01-08.txt |
AC |
3 ms |
384 KB |
01-09.txt |
AC |
3 ms |
256 KB |
01-10.txt |
AC |
3 ms |
384 KB |
01-11.txt |
AC |
3 ms |
384 KB |
01-12.txt |
AC |
3 ms |
384 KB |
01-13.txt |
AC |
3 ms |
384 KB |
01-14.txt |
AC |
3 ms |
256 KB |
01-15.txt |
AC |
3 ms |
384 KB |
01-16.txt |
AC |
3 ms |
384 KB |
01-17.txt |
AC |
3 ms |
384 KB |
01-18.txt |
AC |
3 ms |
384 KB |
01-19.txt |
AC |
3 ms |
256 KB |
01-20.txt |
AC |
3 ms |
384 KB |
01-21.txt |
AC |
3 ms |
384 KB |
01-22.txt |
AC |
3 ms |
256 KB |
01-23.txt |
AC |
3 ms |
256 KB |
01-24.txt |
AC |
3 ms |
384 KB |
01-25.txt |
AC |
3 ms |
384 KB |
01-26.txt |
AC |
3 ms |
256 KB |
01-27.txt |
AC |
3 ms |
256 KB |
01-28.txt |
AC |
3 ms |
384 KB |
01-29.txt |
AC |
3 ms |
384 KB |
01-30.txt |
AC |
3 ms |
384 KB |
01-31.txt |
AC |
3 ms |
256 KB |
01-32.txt |
AC |
3 ms |
384 KB |
01-33.txt |
AC |
3 ms |
256 KB |
01-34.txt |
AC |
3 ms |
384 KB |
01-35.txt |
AC |
3 ms |
384 KB |
01-36.txt |
AC |
3 ms |
384 KB |
01-37.txt |
AC |
3 ms |
256 KB |
01-38.txt |
AC |
3 ms |
384 KB |
01-39.txt |
AC |
3 ms |
384 KB |
01-40.txt |
AC |
3 ms |
384 KB |
01-41.txt |
AC |
3 ms |
384 KB |
01-42.txt |
AC |
3 ms |
384 KB |
01-43.txt |
AC |
3 ms |
384 KB |
01-44.txt |
AC |
3 ms |
384 KB |
01-45.txt |
AC |
3 ms |
384 KB |
01-46.txt |
AC |
3 ms |
384 KB |
02-01.txt |
AC |
31 ms |
1280 KB |
02-02.txt |
AC |
30 ms |
1280 KB |
02-03.txt |
AC |
28 ms |
1280 KB |
02-04.txt |
AC |
32 ms |
1280 KB |
02-05.txt |
AC |
3 ms |
256 KB |
02-06.txt |
AC |
3 ms |
256 KB |
02-07.txt |
AC |
30 ms |
1280 KB |
02-08.txt |
AC |
96 ms |
1664 KB |
02-09.txt |
AC |
39 ms |
1280 KB |
02-10.txt |
AC |
137 ms |
1408 KB |
02-11.txt |
AC |
39 ms |
1280 KB |
02-12.txt |
AC |
136 ms |
1408 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |