Submission #931475

#	Time	Username	Problem	Language	Result	Execution time	Memory
931475		rainboy	여왕벌 (KOI15_queen)	C11	101 / 100	1244 ms	86868 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32
• Subtask 5: 1 / 1