Contest Duration: ~ (local time) (180 minutes)

Submission #1005690

Source Code Expand

Copy
```#include <cstdio>
#include <cmath>

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define inc( i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec( i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

template<typename T> void swap(T & x, T & y) { T t = x; x = y; y = t; return; }
template<typename T> T abs(T x) { return (0 <= x ? x : -x); }
template<typename T> T max(T a, T b) { return (b <= a ? a : b); }
template<typename T> T min(T a, T b) { return (a <= b ? a : b); }
template<typename T> bool setmin(T & a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T & a, T b) { if(b <= a) { return false; } else { a = b; return true; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, u[300], d[300], l[300], r[300];
int dir[300][300];

int uu[300], dd[300], ll[300], rr[300], nn;
bool out[300][300];

void print() {
char cc[] = { '.', '-', 'l', '+' };
inc(i, n) {
inc(j, n) {
printf("%c ", cc[ dir[i][j] ]);
} printf("\n");
} printf("\n");
}

void print2() {
char cc[] = { '^', 'v', '(', '>' };
inc(i, n) {
inc(j, n) {
printf("%c ", cc[ dir[i][j] - 4 ]);
} printf("\n");
} printf("\n");
}

void print3() {
char cc[] = { '^', 'v', '(', '>' };

printf("   "); inc(j, n) { printf("%2d", uu[j]); } printf("\n");

inc(i, n) { printf("%2d ", ll[i]);
inc(j, n) {
printf("%c ", out[i][j] ? '.' : cc[ dir[i][j] - 4 ]);
} printf("%2d\n", rr[i]);
} printf("");

printf("   "); inc(j, n) { printf("%2d", dd[j]); } printf("\n\n");

}

bool vis[300][300];
int ei[300], ej[300];
bool _search(int i, int j, bool i_flag) {
vis[i][j] = true;

if(dir[i][j] == 0) {
dir[i][j] = (i_flag ? 1 : 2);
ei[i]--;
ej[j]--;
return true;
}

if(i_flag) {
inc(ii, n) {
if(! vis[ii][j] && dir[ii][j] == 0) {
if(_search(ii, j, ! i_flag)) { dir[i][j] = 1; return true; }
}
}
inc(ii, n) {
if(! vis[ii][j] && dir[ii][j] / 2 == 0 && ei[ii] != 0) {
if(_search(ii, j, ! i_flag)) { dir[i][j] = 1; return true; }
}
}
inc(ii, n) {
if(! vis[ii][j] && dir[ii][j] / 2 == 0) {
if(_search(ii, j, ! i_flag)) { dir[i][j] = 1; return true; }
}
}
} else {
inc(jj, n) {
if(! vis[i][jj] && dir[i][jj]  == 0) {
if(_search(i, jj, ! i_flag)) { dir[i][j] = 2; return true; }
}
}
inc(jj, n) {
if(! vis[i][jj] && dir[i][jj] % 2 == 0 && ej[jj] != 0) {
if(_search(i, jj, ! i_flag)) { dir[i][j] = 2; return true; }
}
}
inc(jj, n) {
if(! vis[i][jj] && dir[i][jj] % 2 == 0) {
if(_search(i, jj, ! i_flag)) { dir[i][j] = 2; return true; }
}
}
}

return false;
}

bool search(int i, int j, bool i_flag) {
inc(i, n) {
inc(j, n) {
vis[i][j] = false;
}
}
return _search(i, j, i_flag);
}

int main() {
scanf("%d", &n);
inc(i, n) { scanf("%d", &u[i]); }
inc(i, n) { scanf("%d", &d[i]); }
inc(i, n) { scanf("%d", &l[i]); }
inc(i, n) { scanf("%d", &r[i]); }

inc(i, n) { if(u[i] + d[i] > n || l[i] + r[i] > n) { printf("NO\n"); return 0; } }

inc(i, n) {
inc(j, n) {
dir[i][j] = 0;
}
}
inc(i, n) {
inc(j, l[i] + r[i]) { dir[i][j] += 1; } // -
}
inc(j, n) {
inc(i, u[j] + d[j]) { dir[i][j] += 2; } // |
}
inc(i, n) {
inc(j, n) {
if(dir[i][j] == 0) { ei[i]++; ej[j]++; }
}
}
inc(i, n) {
inc(j, n) {
if(dir[i][j] == 3) {
if(! search(i, j, true) && ! search(i, j, false)) { printf("NO\n"); return 0; }
}
}
}

inc(j, n) {
int c = 0;
inc(i, n) {
if(dir[i][j] == 2) { dir[i][j] = (c++ < u[j] ? 4 : 5); }
}
}
inc(i, n) {
int c = 0;
inc(j, n) {
if(dir[i][j] == 1) { dir[i][j] = (c++ < l[i] ? 6 : 7); }
}
}

inc(i, n) {
uu[i] = ll[i] = 0;
dd[i] = rr[i] = n - 1;
}
int pnn = 0;
while(nn < n * n) {
inc(j, n) {
while(uu[j] < n && out[ uu[j] ][j]) { uu[j]++; }
if(uu[j] < n && dir[ uu[j] ][j] == 4) {
printf("U%d\n", j + 1);
out[ uu[j] ][j] = true;
nn++;
}
}
inc(j, n) {
while(dd[j] >= 0 && out[ dd[j] ][j]) { dd[j]--; }
if(dd[j] >= 0 && dir[ dd[j] ][j] == 5) {
printf("D%d\n", j + 1);
out[ dd[j] ][j] = true;
nn++;
}
}
inc(i, n) {
while(ll[i] < n && out[i][ ll[i] ]) { ll[i]++; }
if(ll[i] < n && dir[i][ ll[i] ] == 6) {
printf("L%d\n", i + 1);
out[i][ ll[i] ] = true;
nn++;
}
}
inc(i, n) {
while(rr[i] >= 0 && out[i][ rr[i] ]) { rr[i]--; }
if(rr[i] >= 0 && dir[i][ rr[i] ] == 7) {
printf("R%d\n", i + 1);
out[i][ rr[i] ] = true;
nn++;
}
}

if(nn == pnn) {
inc(i, n) {
inc(j, n) {
vis[i][j] = false;
}
}

inc(j, n) {
if(uu[j] < n) {
int i = uu[j], v;
int di[4] = { -1, 1,  0, 0 };
int dj[4] = {  0, 0, -1, 1 };

do {
vis[i][j] = true;
v = dir[i][j];
do { i += di[v - 4]; j += dj[v - 4]; } while(out[i][j]);
} while(! vis[i][j]);

v = dir[i][j];
int oi = i, oj = j;
do {
do { i += di[v - 4]; j += dj[v - 4]; } while(out[i][j]);
swap(v, dir[i][j]);
} while(i != oi || j != oj);

break;
}
}
}
pnn = nn;
}

return 0;
}
```

#### Submission Info

Submission Time 2016-12-03 02:48:16+0900 J - Neue Spiel FF256grhy C++14 (GCC 5.4.1) 2100 5786 Byte AC 1250 ms 1152 KB

#### Compile Error

```./Main.cpp: In function ‘void print3()’:
./Main.cpp:63:13: warning: zero-length gnu_printf format string [-Wformat-zero-length]
} printf("");
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:128:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:129:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
inc(i, n) { scanf("%d", &u[i]); }
^
./Main.cpp:130:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
inc(i, n) { scanf("%d", &d[i]); }
^
./Main.cpp:131:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
inc(i, n) { scanf("%d", &l[i]); }
...```

#### Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt
dataset1 2000 / 2000 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 100 / 100 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 1 ms 128 KB
01-02.txt 1 ms 128 KB
01-03.txt 1 ms 128 KB
01-04.txt 1 ms 256 KB
01-05.txt 1 ms 256 KB
01-06.txt 2 ms 256 KB
01-07.txt 2 ms 256 KB
01-08.txt 2 ms 256 KB
01-09.txt 1 ms 256 KB
01-10.txt 2 ms 256 KB
01-11.txt 2 ms 256 KB
01-12.txt 2 ms 256 KB
01-13.txt 2 ms 256 KB
01-14.txt 1 ms 128 KB
01-15.txt 2 ms 256 KB
01-16.txt 2 ms 256 KB
01-17.txt 2 ms 256 KB
01-18.txt 2 ms 256 KB
01-19.txt 1 ms 128 KB
01-20.txt 3 ms 256 KB
01-21.txt 2 ms 256 KB
01-22.txt 1 ms 128 KB
01-23.txt 1 ms 128 KB
01-24.txt 3 ms 256 KB
01-25.txt 3 ms 256 KB
01-26.txt 1 ms 128 KB
01-27.txt 2 ms 256 KB
01-28.txt 2 ms 256 KB
01-29.txt 3 ms 256 KB
01-30.txt 2 ms 256 KB
01-31.txt 1 ms 128 KB
01-32.txt 3 ms 256 KB
01-33.txt 1 ms 128 KB
01-34.txt 2 ms 256 KB
01-35.txt 2 ms 256 KB
01-36.txt 2 ms 256 KB
01-37.txt 1 ms 128 KB
01-38.txt 2 ms 256 KB
01-39.txt 2 ms 256 KB
01-40.txt 3 ms 256 KB
01-41.txt 3 ms 256 KB
01-42.txt 3 ms 256 KB
01-43.txt 2 ms 256 KB
01-44.txt 2 ms 256 KB
01-45.txt 2 ms 256 KB
01-46.txt 2 ms 256 KB
02-01.txt 1083 ms 1152 KB
02-02.txt 1058 ms 1152 KB
02-03.txt 331 ms 1152 KB
02-04.txt 1115 ms 1152 KB
02-05.txt 1 ms 128 KB
02-06.txt 1 ms 128 KB
02-07.txt 1122 ms 1152 KB
02-08.txt 1250 ms 1152 KB
02-09.txt 854 ms 1152 KB
02-10.txt 854 ms 1152 KB
02-11.txt 854 ms 1152 KB
02-12.txt 854 ms 1152 KB
sample-01.txt 1 ms 128 KB
sample-02.txt 1 ms 128 KB