이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#define N 200000
#define M (N * 12)
int abs_(int a) { return a > 0 ? a : -a; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
int xx[N], yy[N], uu[N], vv[N], dd[N], n;
int compare_uv(int i, int j) {
return uu[i] != uu[j] ? uu[i] - uu[j] : vv[i] - vv[j];
}
int compare_xy(int i, int j) {
return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j];
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int ii[M], jj[M], tt[M], m;
int iq[M + 1], pq[M], cnt;
int lt(int h1, int h2) { return tt[h1] < tt[h2]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add(int i) {
pq[i] = ++cnt, pq_up(i);
}
int pq_first() {
return iq[1];
}
void pq_remove_first() {
int i = iq[1], j = iq[cnt--];
if (j != i)
pq[j] = 1, pq_dn(j);
pq[i] = 0;
}
void add(int i, int j) {
if (i != -1 && j != -1) {
int t = (abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i])) / 2;
if (xx[i] + dx[dd[i]] * t == xx[j] + dx[dd[j]] * t && yy[i] + dy[dd[i]] * t == yy[j] + dy[dd[j]] * t)
ii[m] = i, jj[m] = j, tt[m] = t, pq_add(m++);
}
}
char dead[N]; int pp[N][6], qq[N][6];
void kill_(int i) {
int h;
if (dead[i])
return;
dead[i] = 1;
for (h = 0; h < 6; h++) {
int p = pp[i][h], q = qq[i][h];
if (p != -1 && q != -1)
qq[p][h] = q, pp[q][h] = p, add(p, q);
}
}
int main() {
static int hh[M];
int cnt_, h, i, j, r, t, tmp;
scanf("%d", &n);
for (i = 0; i < n; i++) {
static char s[2];
scanf("%d%d%s", &xx[i], &yy[i], s);
if (s[0] == 'N')
dd[i] = 0;
else if (s[0] == 'E')
dd[i] = 1;
else if (s[0] == 'S')
dd[i] = 2;
else
dd[i] = 3;
}
for (i = 0; i < n; i++)
for (h = 0; h < 6; h++)
pp[i][h] = qq[i][h] = -1;
for (r = 0; r < 4; r++) {
for (i = 0; i < n; i++)
ii[i] = i;
for (i = 0; i < n; i++)
uu[i] = xx[i] + yy[i], vv[i] = xx[i] - yy[i];
compare = compare_uv, sort(ii, 0, n);
for (h = 0, i = -1; h < n; h++) {
j = ii[h];
if (dd[j] == 1 || dd[j] == 2) {
if (i != -1)
qq[i][r] = j, pp[j][r] = i;
i = j;
}
}
if (r < 2) {
compare = compare_xy, sort(ii, 0, n);
for (h = 0, i = -1; h < n; h++) {
j = ii[h];
if (dd[j] == 0 || dd[j] == 2) {
if (i != -1)
qq[i][4 + r] = j, pp[j][4 + r] = i;
i = j;
}
}
}
for (i = 0; i < n; i++) {
tmp = -xx[i], xx[i] = yy[i], yy[i] = tmp;
dd[i] = (dd[i] + 1) % 4;
}
}
m = 0;
for (i = 0; i < n; i++)
for (h = 0; h < 6; h++)
add(i, qq[i][h]);
while (cnt) {
h = pq_first(), t = tt[h];
if (dead[ii[h]] || dead[jj[h]]) {
pq_remove_first();
continue;
}
cnt_ = 0;
while (cnt && tt[h = pq_first()] == t) {
pq_remove_first();
if (!dead[ii[h]] && !dead[jj[h]])
hh[cnt_++] = h;
}
while (cnt_--) {
h = hh[cnt_];
kill_(ii[h]), kill_(jj[h]);
}
}
for (i = 0; i < n; i++)
if (!dead[i])
printf("%d\n", i + 1);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.c: In function 'main':
Main.c:121:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
Main.c:125:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | scanf("%d%d%s", &xx[i], &yy[i], s);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |