Submission #8661058
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
//#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
os<<"{";
for(auto e:v)os<<e<<",";
return os<<"}";
}
#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ";
dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,"Line:",__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif
using uint=unsigned;
using ull=unsigned long long;
template<int i,class T>
void print_tuple(ostream&,const T&){
}
template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
if(i)os<<",";
os<<get<i>(t);
print_tuple<i+1,T,Args...>(os,t);
}
template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
os<<"{";
print_tuple<0,tuple<Args...>,Args...>(os,t);
return os<<"}";
}
void print(ll x,int suc=1){
cout<<x;
if(suc==1)
cout<<"\n";
if(suc==2)
cout<<" ";
}
ll read(){
ll i;
cin>>i;
return i;
}
vi readvi(int n,int off=0){
vi v(n);
rep(i,n)v[i]=read()+off;
return v;
}
template<class T>
void print(const vector<T>&v,int suc=1){
rep(i,v.size())
print(v[i],i==int(v.size())-1?suc:2);
}
string readString(){
string s;
cin>>s;
return s;
}
template<class T>
T sq(const T& t){
return t*t;
}
//#define CAPITAL
void yes(bool ex=true){
#ifdef CAPITAL
cout<<"YES"<<endl;
#else
cout<<"Yes"<<endl;
#endif
if(ex)exit(0);
}
void no(bool ex=true){
#ifdef CAPITAL
cout<<"NO"<<endl;
#else
cout<<"No"<<endl;
#endif
if(ex)exit(0);
}
constexpr ll ten(int n){
return n==0?1:ten(n-1)*10;
}
const ll infLL=LLONG_MAX/3;
#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif
int topbit(signed t){
return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
return __builtin_popcount(t);
}
int popcount(ll t){
return __builtin_popcountll(t);
}
bool ispow2(int i){
return i&&(i&-i)==i;
}
int mask(int i){
return (int(1)<<i)-1;
}
bool inc(int a,int b,int c){
return a<=b&&b<=c;
}
template<class t> void mkuni(vc<t>&v){
sort(all(v));
v.erase(unique(all(v)),v.ed);
}
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static random_device rd;
static mt19937_64 gen(rd());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
template<class t>
int lwb(const vc<t>&v,const t&a){
return lower_bound(all(v),a)-v.bg;
}
const int nmax=310;
int dp[nmax][nmax][2],pre[nmax][nmax][2];
vi imos(vi x){
vi y{0};
for(auto v:x)
y.pb(y.back()+v);
return y;
}
//AOJGRL4B
template<class t>
vi toposort(vvc<t> g){
int n=g.size();
vi a(n);
rep(i,n)for(auto e:g[i])
a[e]++;
queue<int> q;
rep(i,n)if(a[i]==0)
q.push(i);
vi res;
rep(i,n){
if(q.empty())return {};
int v=q.front();q.pop();
res.pb(v);
for(auto e:g[v])
if(--a[e]==0)
q.push(e);
}
return res;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
int n;cin>>n;
int dbg=n<0;
if(dbg)n=-n;
vi u(n),d(n),l(n),r(n);
if(dbg){
rep(i,n)rep(j,n){
int k=rand_int(0,3);
if(k==0)u[j]++;
else if(k==1)d[j]++;
else if(k==2)l[i]++;
else r[i]++;
}
}else{
u=readvi(n);
d=readvi(n);
l=readvi(n);
r=readvi(n);
}
dmp(u);
dmp(d);
dmp(l);
dmp(r);
vvc<int> tp(n,vi(n,-1));
{
vi v(n),h(n);
rep(i,n)v[i]=u[i]+d[i];
rep(i,n)h[i]=l[i]+r[i];
sort(all(v),greater<int>());
v=imos(v);
sort(all(h),greater<int>());
h=imos(h);
rep(i,n+1)rep(j,n+1){
if(v[i]+h[j]>(i+j)*n-i*j){
cout<<"NO"<<endl;
return 0;
}
}
}
rep(si,n){
vi lim(n+1,inf);
{
vi h;
rng(j,si+1,n)
h.pb(l[j]+r[j]);
sort(all(h),greater<int>());
h=imos(h);
dmp(h);
rep(i,h.size())rep(j,n+1){
int c=i*n+j*(n-1-si)-i*j-h[i];
chmin(lim[j],c);
}
}
dmp(lim);
vi v(n);
iota(all(v),0);
sort(all(v),[&](int a,int b){
int c=u[a]+d[a];
int e=u[b]+d[b];
if(c!=e)return c>e;
else return u[a]<u[b];
});
vi lw(n+1);
{
int s=0;
rep(i,n+1){
lw[i]=max(int(0),s-lim[i]);
if(i)chmax(lw[i],lw[i-1]);
if(i<n)
s+=u[v[i]]+d[v[i]];
}
}
one(dp);
one(pre);
dp[0][0][0]=0;
rep(i,n)rng(j,lw[i],i+1)rep(k,2){
rep(x,2){
if(x==0&&k&&i&&u[v[i-1]]+d[v[i-1]]==u[v[i]]+d[v[i]])
continue;
if(x==1&&u[v[i]]+d[v[i]]==0)
continue;
int w=dp[i][j][k];
if(x&&u[v[i]])w++;
if(dp[i+1][j+x][x]<w){
dp[i+1][j+x][x]=w;
pre[i+1][j+x][x]=(i*n+j)*2+k;
}
}
}
int ci=n,cj=lw[n],ck=0;
if(dp[ci][cj][ck]<dp[ci][cj][ck+1])
ck=1;
dmp(lw);
vi use(n);
per(i,n){
use[v[i]]=ck;
int p=pre[ci][cj][ck];
ck=p%2;p/=2;
cj=p%n;p/=n;
ci=p;
}
dmp(use);
rep(i,n){
if(use[i]){
if(u[i]){
tp[si][i]=0;
u[i]--;
}else{
assert(d[i]);
tp[si][i]=1;
d[i]--;
}
}else{
if(l[si]){
tp[si][i]=2;
l[si]--;
}else{
assert(r[si]);
tp[si][i]=3;
r[si]--;
}
}
}
dmp(tp);
}
assert(u==vi(n,0));
assert(d==vi(n,0));
assert(l==vi(n,0));
assert(r==vi(n,0));
dmp(tp);
vvc<int> g(n*n);
rep(i,n)rep(j,n){
if(tp[i][j]==0){
rep(k,i)
g[k*n+j].pb(i*n+j);
}else if(tp[i][j]==1){
rng(k,i+1,n)
g[k*n+j].pb(i*n+j);
}else if(tp[i][j]==2){
rep(k,j)
g[i*n+k].pb(i*n+j);
}else{
rng(k,j+1,n)
g[i*n+k].pb(i*n+j);
}
}
vi idx=toposort(g);
assert(idx.size());
for(auto x:idx){
int i=x/n,j=x%n;
if(tp[i][j]==0){
cout<<'U'<<j+1<<endl;
}else if(tp[i][j]==1){
cout<<'D'<<j+1<<endl;
}else if(tp[i][j]==2){
cout<<'L'<<i+1<<endl;
}else{
cout<<'R'<<i+1<<endl;
}
}
}
Submission Info
Submission Time |
|
Task |
J - Neue Spiel |
User |
maroonrk |
Language |
C++14 (GCC 5.4.1) |
Score |
2100 |
Code Size |
7106 Byte |
Status |
AC |
Exec Time |
619 ms |
Memory |
139772 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, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
1792 KB |
01-02.txt |
AC |
2 ms |
1792 KB |
01-03.txt |
AC |
2 ms |
1792 KB |
01-04.txt |
AC |
3 ms |
1792 KB |
01-05.txt |
AC |
4 ms |
1792 KB |
01-06.txt |
AC |
6 ms |
1920 KB |
01-07.txt |
AC |
9 ms |
2048 KB |
01-08.txt |
AC |
9 ms |
2048 KB |
01-09.txt |
AC |
4 ms |
1792 KB |
01-10.txt |
AC |
8 ms |
2048 KB |
01-11.txt |
AC |
9 ms |
2048 KB |
01-12.txt |
AC |
9 ms |
2048 KB |
01-13.txt |
AC |
9 ms |
2048 KB |
01-14.txt |
AC |
1 ms |
256 KB |
01-15.txt |
AC |
8 ms |
2048 KB |
01-16.txt |
AC |
9 ms |
2048 KB |
01-17.txt |
AC |
9 ms |
2048 KB |
01-18.txt |
AC |
9 ms |
2048 KB |
01-19.txt |
AC |
1 ms |
256 KB |
01-20.txt |
AC |
9 ms |
2048 KB |
01-21.txt |
AC |
9 ms |
2048 KB |
01-22.txt |
AC |
1 ms |
256 KB |
01-23.txt |
AC |
1 ms |
256 KB |
01-24.txt |
AC |
9 ms |
2048 KB |
01-25.txt |
AC |
9 ms |
2048 KB |
01-26.txt |
AC |
1 ms |
256 KB |
01-27.txt |
AC |
5 ms |
1920 KB |
01-28.txt |
AC |
9 ms |
2048 KB |
01-29.txt |
AC |
9 ms |
2048 KB |
01-30.txt |
AC |
9 ms |
2048 KB |
01-31.txt |
AC |
1 ms |
256 KB |
01-32.txt |
AC |
9 ms |
2048 KB |
01-33.txt |
AC |
1 ms |
256 KB |
01-34.txt |
AC |
9 ms |
2048 KB |
01-35.txt |
AC |
8 ms |
2176 KB |
01-36.txt |
AC |
8 ms |
2176 KB |
01-37.txt |
AC |
1 ms |
256 KB |
01-38.txt |
AC |
9 ms |
2048 KB |
01-39.txt |
AC |
9 ms |
2048 KB |
01-40.txt |
AC |
8 ms |
2048 KB |
01-41.txt |
AC |
9 ms |
2176 KB |
01-42.txt |
AC |
9 ms |
2176 KB |
01-43.txt |
AC |
9 ms |
2176 KB |
01-44.txt |
AC |
8 ms |
2048 KB |
01-45.txt |
AC |
9 ms |
2176 KB |
01-46.txt |
AC |
8 ms |
2048 KB |
02-01.txt |
AC |
583 ms |
75648 KB |
02-02.txt |
AC |
591 ms |
76416 KB |
02-03.txt |
AC |
619 ms |
76160 KB |
02-04.txt |
AC |
595 ms |
83200 KB |
02-05.txt |
AC |
2 ms |
640 KB |
02-06.txt |
AC |
2 ms |
640 KB |
02-07.txt |
AC |
580 ms |
90364 KB |
02-08.txt |
AC |
547 ms |
105848 KB |
02-09.txt |
AC |
565 ms |
139772 KB |
02-10.txt |
AC |
466 ms |
74620 KB |
02-11.txt |
AC |
562 ms |
139772 KB |
02-12.txt |
AC |
465 ms |
74620 KB |
sample-01.txt |
AC |
2 ms |
1792 KB |
sample-02.txt |
AC |
1 ms |
256 KB |