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

Judge Result