oj.uz

Submission #931475

# Submission time Handle Problem Language Result Execution time Memory
931475 2024-02-21T21:37:43 Z rainboy 여왕벌 (KOI15_queen) C
101 / 100
 1244 ms 86868 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N	700
#define L	9	/* L = floor(log2(N)) */
 
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
 
int *ej1[N + 1], *ej2[N + 1], eo[N + 1];
 
void append(int i, int j1, int j2) {
	int o = eo[i]++;
 
	if (o >= 2 && (o & o - 1) == 0) {
		ej1[i] = (int *) realloc(ej1[i], o * 2 * sizeof *ej1[i]);
		ej2[i] = (int *) realloc(ej2[i], o * 2 * sizeof *ej2[i]);
	}
	ej1[i][o] = j1, ej2[i][o] = j2;
}
 
int main() {
	static char dd[3][3][3][N][N];
	static int jj01[N][N + 1], jj02[N][N + 1], jj12[N][N + 1], jjj[L + 1][N][N + 1], aa[N + 1], bb[N + 1][N + 1], cc[N + 1][N + 1], cc_[N + 1][N + 1], ans[N][N + 1];
	int n, q, i, j, j1, j1_, j2, j2_, k0, k1, l, u, v, w, o, c;
 
	scanf("%d%d", &n, &q);
	for (i = 1; i < n; i++)
		for (j = 1; j < n; j++) {
			static char s[28];
 
			scanf("%s", s);
			for (u = 0; u < 3; u++)
				for (v = 0; v < 3; v++)
					for (w = 0; w < 3; w++)
						dd[u][v][w][i][j] = s[(u * 3 + v) * 3 + w];
		}
	for (i = 1; i < n; i++) {
		for (j = n; j >= 1; j--)
			jj01[i][j] = j == n || dd[0][1][1][i][j] != 'L' ? j : jj01[i][j + 1];
		for (j = n; j >= 1; j--)
			jj02[i][j] = j == n || dd[0][2][2][i][j] != 'L' ? j : jj02[i][j + 1];
		for (j = n; j >= 1; j--)
			jj12[i][j] = j == n || dd[1][2][2][i][j] != 'L' ? j : jj12[i][j + 1];
	}
	for (i = 1; i < n; i++)
		for (j2 = 0; j2 <= n; j2++)
			jjj[0][i][j2] = j2 > 0 && (j2 == n || dd[1][1][2][i][j2] == 'U') ? j2 : jj12[i][j2 + 1];
	for (l = 1; 1 << l < n; l++)
		for (i = 1; i + (1 << l) <= n; i++)
			for (j2 = 0; j2 <= n; j2++)
				jjj[l][i][j2] = jjj[l - 1][i + (1 << l - 1)][jjj[l - 1][i][j2]];
	for (i = 0; i <= n; i++) {
		ej1[i] = (int *) malloc(2 * sizeof *ej1[i]);
		ej2[i] = (int *) malloc(2 * sizeof *ej2[i]);
	}
	while (q--) {
		scanf("%d%d%*d", &k0, &k1);
		if (k0 + k1 < n) {
			aa[0] += 2, aa[n - (k0 + k1)]--, aa[n - k0]--;
			i = n - (k0 + k1), j = 0;
			if (i < n)
				bb[i][jjj[0][i][j]]++;
			for (l = L; l >= 0; l--)
				if ((k1 & 1 << l) != 0)
					j = jjj[l][i][j], i += 1 << l;
			if (i < n)
				bb[i][jjj[0][i][j]]--;
			append(i, 0, j);
		} else if (k0 < n) {
			aa[0]++, aa[n - k0]--;
			ans[0][k0 + k1 - n + 1]++;
			i = 1, j = k0 + k1 - n + 1;
			if (i < n)
				bb[i][jjj[0][i][j]]++;
			for (l = L; l >= 0; l--)
				if ((n - k0 - 1 & 1 << l) != 0)
					j = jjj[l][i][j], i += 1 << l;
			if (i < n)
				bb[i][jjj[0][i][j]]--;
			append(i, 0, j);
		} else {
			ans[0][k0 - n + 1]++, ans[0][k0 + k1 - n + 1]++;
			append(1, k0 - n + 1, k0 + k1 - n + 1);
		}
	}
	for (i = 1; i < n; i++)
		aa[i] += aa[i - 1];
	for (i = 0; i < n; i++)
		ans[i][0] += aa[i];
	for (i = 0; i + 1 < n; i++)
		for (j = 0; j <= n; j++)
			bb[i + 1][jjj[0][i + 1][j]] += bb[i][j];
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ans[i][j] += bb[i][j];
	for (i = 1; i < n; i++) {
		for (o = eo[i]; o--; ) {
			j1 = ej1[i][o], j2 = ej2[i][o];
			cc[j1][j2]++;
		}
		for (j1 = 0; j1 <= n; j1++)
			memset(cc_[j1] + j1, 0, (n - j1 + 1) * sizeof *cc_[j1]);
		for (j1 = 0; j1 <= n; j1++)
			for (j2 = j1; j2 <= n; j2++) {
				c = cc[j1][j2];
				if (c == 0)
					continue;
				j1_ = j1, j2_ = j2;
				if (j1 == j2) {
					if (j2 == 0 || j2 < n && dd[0][0][2][i][j2] != 'U')
						j1_ = j2_ = jj02[i][j2 + 1];
				} else if (j1 == 0 || j1 < n && dd[0][0][1][i][j1] != 'U') {
					j1_ = min(j2, jj01[i][j1 + 1]);
					if (j1_ < j2) {
						if (j2 < n && dd[1][1][2][i][j2] != 'U')
							j2_ = jj12[i][j2 + 1];
					} else if (j2 < n) {
						if (dd[0][1][2][i][j2] == 'L')
							j1_ = j2_ = jj02[i][j2 + 1];
						else if (dd[0][1][2][i][j2] == 'D')
							j2_ = jj12[i][j2 + 1];
					}
				} else {
					if (j2 < n && dd[1][1][2][i][j2] != 'U')
						j2_ = jj12[i][j2 + 1];
				}
				cc_[j1_][j2_] += c;
				ans[i][j1_] += c, ans[i][j2_] += c;
			}
		for (j1 = 0; j1 <= n; j1++)
			memcpy(cc[j1] + j1, cc_[j1] + j1, (n - j1 + 1) * sizeof *cc_[j1]);
	}
	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 'append':
queen.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
queen.c: In function 'main':
queen.c:53:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |     jjj[l][i][j2] = jjj[l - 1][i + (1 << l - 1)][jjj[l - 1][i][j2]];
      |                                          ~~^~~
queen.c:78:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   78 |     if ((n - k0 - 1 & 1 << l) != 0)
      |          ~~~~~~~^~~
queen.c:112:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  112 |      if (j2 == 0 || j2 < n && dd[0][0][2][i][j2] != 'U')
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
queen.c:114:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  114 |     } else if (j1 == 0 || j1 < n && dd[0][0][1][i][j1] != 'U') {
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
queen.c:28:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
queen.c:33:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |    scanf("%s", s);
      |    ^~~~~~~~~~~~~~
queen.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d%d%*d", &k0, &k1);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 7 ms 36036 KB Output is correct
4 Correct 7 ms 35932 KB Output is correct
5 Correct 37 ms 41668 KB Output is correct
6 Correct 35 ms 41808 KB Output is correct
7 Correct 35 ms 41820 KB Output is correct
8 Correct 110 ms 45904 KB Output is correct
9 Correct 110 ms 45908 KB Output is correct
10 Correct 244 ms 46820 KB Output is correct
11 Correct 246 ms 60388 KB Output is correct
12 Correct 256 ms 60240 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 36 ms 43432 KB Output is correct
3 Correct 69 ms 44528 KB Output is correct
4 Correct 253 ms 48596 KB Output is correct
5 Correct 246 ms 48416 KB Output is correct
6 Correct 255 ms 48720 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 9 ms 37976 KB Output is correct
3 Correct 131 ms 47008 KB Output is correct
4 Correct 277 ms 48976 KB Output is correct
5 Correct 269 ms 62228 KB Output is correct
6 Correct 266 ms 62208 KB Output is correct
7 Correct 273 ms 62292 KB Output is correct
8 Correct 279 ms 62212 KB Output is correct
9 Correct 266 ms 62148 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 57940 KB Output is correct
2 Correct 345 ms 57652 KB Output is correct
3 Correct 1244 ms 61596 KB Output is correct
4 Correct 532 ms 86440 KB Output is correct
5 Correct 508 ms 86316 KB Output is correct
6 Correct 545 ms 86640 KB Output is correct
7 Correct 550 ms 86196 KB Output is correct
8 Correct 487 ms 85588 KB Output is correct
9 Correct 470 ms 85332 KB Output is correct
10 Correct 547 ms 86344 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 175 ms 37912 KB Output is correct
6 Correct 176 ms 38128 KB Output is correct
7 Correct 183 ms 40388 KB Output is correct
8 Correct 182 ms 40012 KB Output is correct
9 Correct 481 ms 74272 KB Output is correct
10 Correct 1217 ms 74332 KB Output is correct
11 Correct 1205 ms 86800 KB Output is correct
12 Correct 515 ms 86412 KB Output is correct
13 Correct 524 ms 86352 KB Output is correct
14 Correct 479 ms 86700 KB Output is correct
15 Correct 1229 ms 86728 KB Output is correct
16 Correct 1211 ms 86616 KB Output is correct
17 Correct 556 ms 86868 KB Output is correct
18 Correct 516 ms 86488 KB Output is correct