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
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
AC × 2
AC × 48
AC × 60
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