Submission #1025792
Source Code Expand
#include<cassert>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 305;
int n, u[N], d[N], l[N], r[N],
cu[N], cd[N], rl[N], rr[N];
int ma[N][N], row[N], col[N];
const int dx[4] = {-1, 0, 1, 0},
dy[4] = {0, 1, 0, -1};
const char DC[] = "URDL";
int dir[N][N];
bool taken[N][N];
int tot;
int vis[N][N], mark[N][N], stamp;
void update(int x, int y) {
++tot;
int d = dir[x][y];
taken[x][y] = true;
int tx = x + dx[d], ty = y + dy[d];
assert(tx < 0 || tx >= n || ty < 0 || ty >= n || taken[tx][ty]);
printf("%c%d\n", DC[d], (d & 1) ? (x + 1) : (y + 1));
while (cu[y] < n && taken[cu[y]][y]) {
++cu[y];
}
while (cd[y] < n && taken[n - 1 - cd[y]][y]) {
++cd[y];
}
while (rl[x] < n && taken[x][rl[x]]) {
++rl[x];
}
while (rr[x] < n && taken[x][n - 1 - rr[x]]) {
++rr[x];
}
}
void twist(int i, int j) {
++stamp;
int x = i, y = j, step = 0;
vector<pair<int, int> > stack;
while (true) {
//cout << x << ' ' << y << endl;
//cout << cu[y] << ' ' << cd[y] << ' ' << rl[x] << ' ' << rr[x] << endl;
assert(!taken[x][y]);
stack.push_back(make_pair(x, y));
vis[x][y] = stamp;
mark[x][y] = step++;
int d = dir[x][y], tx, ty;
if (d == 0) {
tx = cu[y], ty = y;
} else if (d == 1) {
tx = x, ty = n - 1 - rr[x];
} else if (d == 2) {
tx = n - 1 - cd[y], ty = y;
} else { //if (d == 3) {
tx = x, ty = rl[x];
}
x = tx, y = ty;
if (vis[tx][ty] == stamp) {
break;
}
}
int tmp = dir[stack.back().first][stack.back().second];
for (int i = step - 1; i - 1 >= mark[x][y]; --i) {
int x = stack[i].first, y = stack[i].second,
tx = stack[i - 1].first, ty = stack[i - 1].second;
dir[x][y] = dir[tx][ty];
}
dir[x][y] = tmp;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", u + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d", d + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d", l + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d", r + i);
}
bool flag = true;
for (int i = 0; i < n; ++i) {
row[i] = l[i] + r[i];
col[i] = u[i] + d[i];
if (row[i] > n || col[i] > n) {
flag = false;
}
col[i] = n - col[i];
}
if (!flag) {
puts("NO");
return 0;
}
priority_queue<pair<int, int> > heap;
for (int i = 0; i < n; ++i) {
if (col[i] > 0) {
heap.push(make_pair(col[i], i));
}
}
for (int i = 0; i < n; ++i) {
int crow = -1;
for (int j = 0; j < n; ++j) {
if (row[j] > 0 && (crow == -1 || row[crow] < row[j])) {
crow = j;
}
}
if (crow == -1) {
break;
}
if (row[crow] > (int)heap.size()) {
puts("NO");
return 0;
}
vector<pair<int, int> > left;
for (int j = 0; j < row[crow]; ++j) {
pair<int, int> ccol = heap.top();
heap.pop();
ma[crow][ccol.second] = 1;
//cout << crow << ' ' << ccol.second << endl;
--ccol.first;
if (ccol.first > 0) {
left.push_back(ccol);
}
}
row[crow] = 0;
for (int j = 0; j < (int)left.size(); ++j) {
heap.push(left[j]);
}
}
for (int i = 0; i < n; ++i) {
int cnt = u[i];
for (int j = 0; j < n; ++j) {
if (ma[j][i] == 0) {
if (cnt) {
dir[j][i] = 0;
--cnt;
} else {
dir[j][i] = 2;
}
}
}
cnt = l[i];
for (int j = 0; j < n; ++j) {
if (ma[i][j] == 1) {
if (cnt) {
dir[i][j] = 3;
--cnt;
} else {
dir[i][j] = 1;
}
}
}
}
tot = 0;
int lx = 0, ly = 0;
while (tot < n * n) {
/*
for (int k = 0; k < n; ++k) {
for (int l = 0; l < n; ++l) {
printf("%c", DC[dir[k][l]]);
}
printf("\n");
}
*/
bool flag = true;
for (int i = 0; i < n; ++i) {
if (cu[i] < n && dir[cu[i]][i] == 0) {
update(cu[i], i);
flag = false;
}
}
for (int i = 0; i < n; ++i) {
if (cd[i] < n && dir[n - 1 - cd[i]][i] == 2) {
update(n - 1 - cd[i], i);
flag = false;
}
}
for (int i = 0; i < n; ++i) {
if (rl[i] < n && dir[i][rl[i]] == 3) {
update(i, rl[i]);
flag = false;
}
}
for (int i = 0; i < n; ++i) {
if (rr[i] < n && dir[i][n - 1 - rr[i]] == 1) {
update(i, n - 1 - rr[i]);
flag = false;
}
}
if (flag) {
while (taken[lx][ly]) {
++ly;
if (ly == n) {
++lx, ly = 0;
}
}
twist(lx, ly);
}
}
return 0;
}
Submission Info
Submission Time
2016-12-16 01:17:03+0900
Task
J - Neue Spiel
User
TankEngineer
Language
C++14 (GCC 5.4.1)
Score
2100
Code Size
4494 Byte
Status
AC
Exec Time
74 ms
Memory
2176 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:89:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", u + i);
^
./Main.cpp:92:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", d + i);
^
./Main.cpp:95:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", l + i);
^
./Main.cpp:98:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", r + i);
^
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
384 KB
01-06.txt
AC
3 ms
384 KB
01-07.txt
AC
3 ms
512 KB
01-08.txt
AC
3 ms
384 KB
01-09.txt
AC
3 ms
384 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
512 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
512 KB
01-25.txt
AC
3 ms
512 KB
01-26.txt
AC
3 ms
256 KB
01-27.txt
AC
3 ms
384 KB
01-28.txt
AC
3 ms
512 KB
01-29.txt
AC
3 ms
512 KB
01-30.txt
AC
3 ms
512 KB
01-31.txt
AC
3 ms
256 KB
01-32.txt
AC
3 ms
512 KB
01-33.txt
AC
3 ms
256 KB
01-34.txt
AC
3 ms
512 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
512 KB
01-41.txt
AC
3 ms
512 KB
01-42.txt
AC
3 ms
512 KB
01-43.txt
AC
3 ms
384 KB
01-44.txt
AC
3 ms
512 KB
01-45.txt
AC
3 ms
384 KB
01-46.txt
AC
3 ms
512 KB
02-01.txt
AC
30 ms
1664 KB
02-02.txt
AC
32 ms
1664 KB
02-03.txt
AC
22 ms
1664 KB
02-04.txt
AC
33 ms
1792 KB
02-05.txt
AC
3 ms
256 KB
02-06.txt
AC
3 ms
256 KB
02-07.txt
AC
34 ms
1536 KB
02-08.txt
AC
64 ms
2176 KB
02-09.txt
AC
18 ms
1536 KB
02-10.txt
AC
74 ms
2176 KB
02-11.txt
AC
18 ms
1536 KB
02-12.txt
AC
74 ms
2176 KB
sample-01.txt
AC
3 ms
256 KB
sample-02.txt
AC
3 ms
256 KB