oj.uz

Submission #931446

# Submission time Handle Problem Language Result Execution time Memory
931446 2024-02-21T19:55:56 Z rainboy 여왕벌 (KOI15_queen) C
68 / 100
 5000 ms 31708 KB 
#include <stdio.h>

#define N	700

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static char cc[3][3][3][N][N];
	static int jj01[N][N + 1], jj02[N][N + 1], jj12[N][N + 1], ans[N][N + 1];
	int n, k, i, j, j1, j2, a, b, c;

	scanf("%d%d", &n, &k);
	for (i = 1; i < n; i++)
		for (j = 1; j < n; j++) {
			static char s[28];

			scanf("%s", s);
			for (a = 0; a < 3; a++)
				for (b = 0; b < 3; b++)
					for (c = 0; c < 3; c++)
						cc[a][b][c][i][j] = s[(a * 3 + b) * 3 + c];
		}
	for (i = 1; i < n; i++) {
		for (j = n; j >= 1; j--)
			jj01[i][j] = j == n || cc[0][1][1][i][j] != 'L' ? j : jj01[i][j + 1];
		for (j = n; j >= 1; j--)
			jj02[i][j] = j == n || cc[0][2][2][i][j] != 'L' ? j : jj02[i][j + 1];
		for (j = n; j >= 1; j--)
			jj12[i][j] = j == n || cc[1][2][2][i][j] != 'L' ? j : jj12[i][j + 1];
	}
	while (k--) {
		int x, y;

		scanf("%d%d%*d", &x, &y), y += x;
		j1 = max(x - (n - 1), 0), j2 = max(y - (n - 1), 0);
		ans[0][j1]++, ans[0][j2]++;
		for (i = 1; i < n; i++) {
			if (n - i <= x) {
				if (j1 == j2) {
					if (j2 == 0 || j2 < n && cc[0][0][2][i][j2] != 'U')
						j1 = j2 = jj02[i][j2 + 1];
				} else if (j1 == 0 || j1 < n && cc[0][0][1][i][j1] != 'U') {
					j1 = min(j2, jj01[i][j1 + 1]);
					if (j1 < j2) {
						if (j2 < n && cc[1][1][2][i][j2] != 'U')
							j2 = jj12[i][j2 + 1];
					} else if (j2 < n) {
						if (cc[0][1][2][i][j2] == 'L')
							j1 = j2 = jj02[i][j2 + 1];
						else if (cc[0][1][2][i][j2] == 'D')
							j2 = jj12[i][j2 + 1];
					}
				} else {
					if (j2 < n && cc[1][1][2][i][j2] != 'U')
						j2 = jj12[i][j2 + 1];
				}
			} else if (n - i <= y) {
				if (j2 == 0 || j2 < n && cc[1][1][2][i][j2] != 'U')
					j2 = jj12[i][j2 + 1];
			}
			ans[i][j1]++, ans[i][j2]++;
		}
	}
	for (i = 0; i < n; i++)
		for (j = 1; j < n; j++)
			ans[i][j] += ans[i][j - 1];
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ans[i][j]++;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			printf("%d ", ans[i][j]);
		printf("\n");
	}
	return 0;
}

Compilation message

queen.c: In function 'main':
queen.c:41:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |      if (j2 == 0 || j2 < n && cc[0][0][2][i][j2] != 'U')
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
queen.c:43:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |     } else if (j1 == 0 || j1 < n && cc[0][0][1][i][j1] != 'U') {
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
queen.c:59:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |     if (j2 == 0 || j2 < n && cc[1][1][2][i][j2] != 'U')
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
queen.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
queen.c:18:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |    scanf("%s", s);
      |    ^~~~~~~~~~~~~~
queen.c:35:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d%d%*d", &x, &y), y += x;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18776 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 4 ms 19544 KB Output is correct
4 Correct 4 ms 19544 KB Output is correct
5 Correct 18 ms 21764 KB Output is correct
6 Correct 18 ms 21596 KB Output is correct
7 Correct 17 ms 21852 KB Output is correct
8 Correct 44 ms 24768 KB Output is correct
9 Correct 43 ms 24612 KB Output is correct
10 Correct 84 ms 29012 KB Output is correct
11 Correct 82 ms 28860 KB Output is correct
12 Correct 82 ms 28756 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 29 ms 21920 KB Output is correct
3 Correct 42 ms 23632 KB Output is correct
4 Correct 136 ms 30184 KB Output is correct
5 Correct 114 ms 30236 KB Output is correct
6 Correct 125 ms 30544 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 10 ms 19548 KB Output is correct
3 Correct 92 ms 25568 KB Output is correct
4 Correct 166 ms 30544 KB Output is correct
5 Correct 164 ms 30408 KB Output is correct
6 Correct 166 ms 30420 KB Output is correct
7 Correct 133 ms 30600 KB Output is correct
8 Correct 121 ms 30540 KB Output is correct
9 Correct 121 ms 30428 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2472 ms 22500 KB Output is correct
2 Correct 2178 ms 31708 KB Output is correct
3 Correct 3360 ms 24660 KB Output is correct
4 Execution timed out 5008 ms 21024 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18776 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Correct 4 ms 18896 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 161 ms 18880 KB Output is correct
6 Correct 158 ms 18884 KB Output is correct
7 Correct 160 ms 18776 KB Output is correct
8 Correct 164 ms 18776 KB Output is correct
9 Correct 1413 ms 24660 KB Output is correct
10 Correct 3504 ms 24604 KB Output is correct
11 Correct 2345 ms 24860 KB Output is correct
12 Execution timed out 5039 ms 20956 KB Time limit exceeded
13 Halted 0 ms 0 KB -