Submission #49664

#	Time	Username	Problem	Language	Result	Execution time	Memory
49664		gs14004	Circle selection (APIO18_circle_selection)	C++17	100 / 100	3570 ms	231144 KiB

circle_selection

#include<cstdio>
#include<algorithm>
#define N_ 301000
using namespace std;
struct Circle {
    int x, y, r, num;
    bool operator<(const Circle &p)const {
        return r != p.r ? r > p.r:num < p.num;
    }
}w[N_];
int n, Res[N_], INF = 1e9, U[22][1<<21], UF[N_*4][22];
struct point {
    int x, y, num;
    bool operator<(const point &p)const {
        return x != p.x ? x < p.x : y < p.y;
    }
}P[N_*4];
bool Intersect(int a, int b) {
    long long dx = w[a].x - w[b].x, dy = w[a].y - w[b].y, dr = w[a].r + w[b].r;
    if (dx*dx + dy*dy <= dr*dr)return true;
    return false;
}
void Chk(int a, int b) {
    if (Res[w[b].num])return;
    if (Intersect(a, b))Res[w[b].num] = w[a].num;
}
int Find(int a, int pv) {
    if (a == UF[a][pv])return a;
    return UF[a][pv] = Find(UF[a][pv], pv);
}
void Del(int a, int pv) {
    UF[a][pv] = Find(UF[a + 1][pv], pv);
}
void Do2(int a, int nd, int pv) {
    int bb;
    int y1 = w[a].y - w[a].r, y2 = w[a].y + w[a].r;
    if (pv >= 3) {
        int b = (nd << pv), e = ((nd + 1) << pv) - 1;
        bb = e + 1;
        int mid;
        while (b <= e) {
            mid = (b + e) >> 1;
            if (P[U[pv][mid]].y >= y1) {
                bb = mid;
                e = mid - 1;
            }
            else b = mid + 1;
        }
    }
    else {
        bb = (nd << pv);
    }
    int e = ((nd + 1) << pv);
    while (1) {
        bb = Find(bb, pv);
        if (bb >= e)break;
        int t = U[pv][bb];
        if (P[t].y > y2)break;
        int tt = P[t].num;
        Chk(a, tt);
        if (Res[w[tt].num])Del(bb, pv);
        bb++;
    }
}
void Do(int a, int b, int e) {
    int pv = 0;
    while (b <= e) {
        if (b & 1) {
            Do2(a, b, pv);
        }
        if (!(e & 1)) {
            Do2(a, e, pv);
        }
        b = (b + 1) >> 1;
        e = (e - 1) >> 1;
        pv++;
    }
}
void Go(int a, int bx, int ex, int by, int ey) {
    point tp = { bx,-INF * 2 - 1, -1 };
    int b = lower_bound(P + 1, P + n * 4 + 1, tp) - P;
    tp = { ex + 1, -INF * 2 - 1, -1 };
    int e = lower_bound(P + 1, P + n * 4 + 1, tp) - P - 1;
    Do(a, b - 1, e - 1);
}
int main() {
    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
        w[i].num = i;
    }
    sort(w + 1, w + n + 1);
    for (i = 1; i <= n; i++) {
        P[i] = { w[i].x - w[i].r,w[i].y - w[i].r,i };
        P[i+n] = { w[i].x - w[i].r,w[i].y + w[i].r,i };
        P[i+n+n] = { w[i].x + w[i].r,w[i].y - w[i].r,i };
        P[i+n+n+n] = { w[i].x + w[i].r,w[i].y + w[i].r,i };
    }
    sort(P + 1, P + n*4 + 1);
    for (i = 0; i < n * 4; i++) {
        U[0][i] = i + 1;
    }
    for (i = 0; i < 20; i++) {
        for (j = 0; j < n * 4; j += (1 << (i + 1))) {
            int mid = j + (1 << i), ed = j + (1 << (i + 1));
            int p1 = j, p2 = mid, pv = j;
            while (p1 < mid || p2 < ed) {
                if (p2 == ed || (p1 != mid && P[U[i][p1]].y < P[U[i][p2]].y)) {
                    U[i + 1][pv++] = U[i][p1++];
                }
                else {
                    U[i + 1][pv++] = U[i][p2++];
                }
            }
        }
    }
    for (i = 0; i <= n * 4 + 10; i++) {
        for (j = 0; j <= 20; j++)UF[i][j] = i;
    }
    for (i = 1; i <= n; i++) {
        if (Res[w[i].num])continue;
        Res[w[i].num] = w[i].num;
        Go(i, w[i].x - w[i].r, w[i].x + w[i].r, w[i].y - w[i].r, w[i].y + w[i].r);
    }
    for (i = 1; i <= n; i++)printf("%d ", Res[i]);
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13