oj.uz

답안 #931472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931472 2024-02-21T21:27:19 Z rainboy 여왕벌 (KOI15_queen) C
24 / 100
 820 ms 59708 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][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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 7 ms 35992 KB Output is correct
4 Correct 6 ms 35932 KB Output is correct
5 Correct 34 ms 41820 KB Output is correct
6 Correct 33 ms 41820 KB Output is correct
7 Correct 35 ms 41812 KB Output is correct
8 Correct 107 ms 43904 KB Output is correct
9 Correct 115 ms 44080 KB Output is correct
10 Incorrect 244 ms 44900 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 38 ms 43420 KB Output is correct
3 Correct 74 ms 44116 KB Output is correct
4 Correct 248 ms 46628 KB Output is correct
5 Correct 251 ms 46596 KB Output is correct
6 Correct 251 ms 46568 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 10 ms 37840 KB Output is correct
3 Correct 116 ms 45136 KB Output is correct
4 Incorrect 259 ms 46804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 55620 KB Output is correct
2 Correct 370 ms 55812 KB Output is correct
3 Incorrect 820 ms 59708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 26968 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 27132 KB Output is correct
4 Correct 4 ms 27088 KB Output is correct
5 Correct 175 ms 34988 KB Output is correct
6 Correct 176 ms 35000 KB Output is correct
7 Correct 174 ms 36936 KB Output is correct
8 Correct 175 ms 37060 KB Output is correct
9 Correct 474 ms 59396 KB Output is correct
10 Incorrect 803 ms 59600 KB Output isn't correct
11 Halted 0 ms 0 KB -