Submission #1217492

#TimeUsernameProblemLanguageResultExecution timeMemory
1217492gs12117Circle selection (APIO18_circle_selection)C++20
7 / 100
3096 ms55324 KiB
#include<cstdio> #include<algorithm> int n; struct circ { long long int x, y, r, idx; bool operator<(const circ& rhs)const { if (r != rhs.r)return r > rhs.r; return idx < rhs.idx; } }; circ c[300100]; circ sc[300100]; struct squ { long long int lx, rx, ly, ry; }; int clist[7501000]; squ sqlist[7501000]; int sqln; int cls[7501000]; int nclist[7501000]; squ nsqlist[7501000]; int nsqln; int ncls[7501000]; long long int sqr; int circsq[300100][25]; int circsql[300100]; int cchk[300100]; int ans[300100]; bool overlap(circ cir, squ sq) { bool xrange = false; bool yrange = false; if (cir.x >= sq.lx && cir.x <= sq.rx) { xrange = true; } if (cir.y >= sq.ly && cir.y <= sq.ry) { yrange = true; } if (xrange && yrange)return true; if (xrange) { if (cir.y + cir.r >= sq.ly && cir.y - cir.r <= sq.ry) { return true; } return false; } if (yrange) { if (cir.x + cir.r >= sq.lx && cir.x - cir.r <= sq.rx) { return true; } return false; } long long int lxdist = cir.x - sq.lx; long long int rxdist = cir.x - sq.rx; if (lxdist < 0)lxdist = -lxdist; if (rxdist < 0)rxdist = -rxdist; if (lxdist < rxdist)rxdist = lxdist; long long int lydist = cir.y - sq.ly; long long int rydist = cir.y - sq.ry; if (lydist < 0)lydist = -lydist; if (rydist < 0)rydist = -rydist; if (lydist < rydist)rydist = lydist; if (cir.r * cir.r >= rxdist * rxdist + rydist * rydist) { return true; } return false; } void inssq(squ sq, int s, int e) { nsqlist[nsqln] = sq; ncls[nsqln + 1] = ncls[nsqln]; nsqln++; for (int i = s; i < e; i++) { int x = clist[i]; if (cchk[x])continue; if (overlap(c[x], sq)) { nclist[ncls[nsqln]] = x; ncls[nsqln]++; } } if (ncls[nsqln] == ncls[nsqln - 1])nsqln--; } void cutsq() { sqr /= 2; nsqln = 0; ncls[0] = 0; for (int i = 0; i < sqln; i++) { squ csq = sqlist[i]; long long int mx = (csq.lx + csq.rx) / 2; long long int my = (csq.ly + csq.ry) / 2; squ nsq; nsq.lx = csq.lx; nsq.rx = mx; nsq.ly = csq.ly; nsq.ry = my; inssq(nsq, cls[i], cls[i + 1]); nsq.lx = csq.lx; nsq.rx = mx; nsq.ly = my; nsq.ry = csq.ry; inssq(nsq, cls[i], cls[i + 1]); nsq.lx = mx; nsq.rx = csq.rx; nsq.ly = csq.ly; nsq.ry = my; inssq(nsq, cls[i], cls[i + 1]); nsq.lx = mx; nsq.rx = csq.rx; nsq.ly = my; nsq.ry = csq.ry; inssq(nsq, cls[i], cls[i + 1]); } sqln = nsqln; for (int i = 0; i < sqln; i++) { cls[i] = ncls[i]; sqlist[i] = nsqlist[i]; } cls[sqln] = ncls[sqln]; for (int i = 0; i < cls[sqln]; i++) { clist[i] = nclist[i]; } for (int i = 0; i < n; i++) { circsql[i] = 0; } for (int i = 0; i < sqln; i++) { for (int j = cls[i]; j < cls[i + 1]; j++) { circsq[clist[j]][circsql[clist[j]]] = i; circsql[clist[j]]++; } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld%lld%lld", &c[i].x, &c[i].y, &c[i].r); c[i].idx = i; sc[i] = c[i]; } std::sort(sc, sc + n); sqln = 1; sqlist[0].rx = (1LL << 32); sqlist[0].ry = sqlist[0].rx; sqlist[0].lx = -sqlist[0].rx; sqlist[0].ly = -sqlist[0].rx; for (int i = 0; i < n; i++) { clist[i] = i; circsq[i][0] = 0; circsql[i] = 1; } cls[0] = 0; cls[1] = n; sqr = sqlist[0].rx - sqlist[0].lx; for (int i = 0; i < n; i++) { int cidx = sc[i].idx; if (cchk[cidx] == 1)continue; cchk[cidx] = 1; ans[cidx] = cidx; long long int circr = sc[i].r; while (circr > sqr) { cutsq(); } for (int j = 0; j < circsql[cidx]; j++) { int sqidx = circsq[cidx][j]; for (int k = cls[sqidx]; k < cls[sqidx + 1]; k++) { int x = clist[k]; if (cchk[x] == 1)continue; if ((c[x].r + c[cidx].r) * (c[x].r + c[cidx].r) >= (c[x].x - c[cidx].x) * (c[x].x - c[cidx].x) + (c[x].y - c[cidx].y) * (c[x].y - c[cidx].y)) { cchk[x] = 1; ans[x] = cidx; } } } } for (int i = 0; i < n; i++) { printf("%d ", ans[i] + 1); } printf("\n"); return 0; }

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
circle_selection.cpp:132:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |                 scanf("%lld%lld%lld", &c[i].x, &c[i].y, &c[i].r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...