| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 931473 |
2024-02-21T21:28:01 Z |
rainboy |
여왕벌 (KOI15_queen) |
C |
|
895 ms |
73104 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 800
#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);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
35160 KB |
Output is correct |
| 2 |
Correct |
4 ms |
35160 KB |
Output is correct |
| 3 |
Correct |
10 ms |
44124 KB |
Output is correct |
| 4 |
Correct |
8 ms |
44124 KB |
Output is correct |
| 5 |
Correct |
35 ms |
55636 KB |
Output is correct |
| 6 |
Correct |
35 ms |
55644 KB |
Output is correct |
| 7 |
Correct |
39 ms |
55544 KB |
Output is correct |
| 8 |
Correct |
112 ms |
57712 KB |
Output is correct |
| 9 |
Correct |
108 ms |
57508 KB |
Output is correct |
| 10 |
Incorrect |
252 ms |
58000 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
37468 KB |
Output is correct |
| 2 |
Correct |
39 ms |
57316 KB |
Output is correct |
| 3 |
Correct |
71 ms |
58088 KB |
Output is correct |
| 4 |
Correct |
256 ms |
59852 KB |
Output is correct |
| 5 |
Correct |
258 ms |
59988 KB |
Output is correct |
| 6 |
Correct |
253 ms |
59836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
37464 KB |
Output is correct |
| 2 |
Correct |
10 ms |
45860 KB |
Output is correct |
| 3 |
Correct |
123 ms |
58672 KB |
Output is correct |
| 4 |
Incorrect |
263 ms |
60036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
69352 KB |
Output is correct |
| 2 |
Correct |
359 ms |
69204 KB |
Output is correct |
| 3 |
Incorrect |
895 ms |
72964 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
3 ms |
31068 KB |
Output is correct |
| 3 |
Correct |
4 ms |
31168 KB |
Output is correct |
| 4 |
Correct |
4 ms |
31068 KB |
Output is correct |
| 5 |
Correct |
180 ms |
39016 KB |
Output is correct |
| 6 |
Correct |
175 ms |
38980 KB |
Output is correct |
| 7 |
Correct |
176 ms |
41248 KB |
Output is correct |
| 8 |
Correct |
185 ms |
41256 KB |
Output is correct |
| 9 |
Correct |
483 ms |
72532 KB |
Output is correct |
| 10 |
Incorrect |
821 ms |
73104 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
