Submission #393318

#	Time	Username	Problem	Language	Result	Execution time	Memory
393318		parsabahrami	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3084 ms	8192 KiB

circle_selection

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 10, MOD = 1e9 + 7;
int n, X[N], Y[N], R[N], ord[N], ret[N];

int intersect(int i, int j) {
    ll x1 = X[i], x2 = X[j], y1 = Y[i], y2 = Y[j], r1 = R[i], r2 = R[j];
    return x1 * x1 + x2 * x2 + y1 * y1 + y2 * y2 - r1 * r1 - r2 * r2 <= 2 * (r1 * r2 + x1 * x2 + y1 * y2);
}

void sub1() {
    for (int _ = 1; _ <= n; _++) {
        int i = ord[_]; 
        if (ret[i]) continue; 
        ret[i] = i;
        for (int j = _ + 1; j <= n; j++) {
            if (!ret[ord[j]] && intersect(i, ord[j])) ret[ord[j]] = i;
        }
    }
    for (int i = 1; i <= n; i++) 
        printf("%d ", ret[i]);
    printf("\n");
    exit(0);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &X[i], &Y[i], &R[i]);
    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [&] (int i, int j) { return R[i] == R[j] ? i < j : R[i] > R[j]; });
    if (n * n <= 1e8) sub1();
    stack<int> st;
    ret[ord[1]] = ord[1]; st.push(ord[1]);
    for (int _ = 2; _ <= n; _++) {
        int i = ord[_];
        while (SZ(st) && !intersect(st.top(), i)) 
            st.pop();
        if (SZ(st)) ret[i] = st.top();
        else ret[i] = i, st.push(i);
    }
    for (int i = 1; i <= n; i++) printf("%d ", ret[i]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%d%d%d", &X[i], &Y[i], &R[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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