Submission #679050

#	Time	Username	Problem	Language	Result	Execution time	Memory
679050		Cross_Ratio	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1833 ms	238172 KiB

circle_selection

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 3> A[300005];
const int INF = 2e9 + 1;
unordered_map<int, vector<int>> M[31];
int pw2[33];
int ans[300005];
int dx[9] = {-1,-1,-1,0,0,0,1,1,1};
int dy[9] = {-1,0,1,-1,0,1,-1,0,1};
bool inter(int a, int b) {
    int k = 1LL * (A[a][0]-A[b][0])*(A[a][0]-A[b][0]);
    k += 1LL * (A[a][1]-A[b][1])*(A[a][1]-A[b][1]);
    return k <= 1LL*(A[a][2]+A[b][2])*(A[a][2]+A[b][2]);
}
bool vis[33];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, j;
    pw2[0] = 1;
    for(i=1;i<33;i++) pw2[i] = pw2[i-1] * 2;
    int N;
    cin >> N;
    for(i=0;i<N;i++) cin >> A[i][0] >> A[i][1] >> A[i][2];
    for(i=0;i<N;i++) {
        A[i][0] += (int)1e9;
        A[i][1] += (int)1e9;
    }
    vector<array<int, 2>> V;
    for(i=0;i<N;i++) V.push_back({A[i][2], i});
    sort(V.begin(),V.end(), [](array<int, 2> x, array<int,2> y) {
         if(x[0]==y[0]) return x[1]<y[1];
         return x[0]>y[0];
         });
    for(i=0;i<N;i++) ans[i] = -1;
    for(i=0;i<N;i++) {
        int id = V[i][1];
        if(ans[id]!=-1) continue;
        ans[id] = id;
        int k = 0;
        while(2*A[id][2]>pw2[k+1]) k++;
        if(!vis[k]) {
            for(j=0;j<N;j++) {
                if(ans[j]!=-1) continue;
                M[k][INF*(A[j][0]/pw2[k+1])+A[j][1]/pw2[k+1]].push_back(j);
            }
            vis[k] = true;
        }
        //cout << id << ' ' << k << '\n';
        int x1 = A[id][0]/pw2[k+1], x2 = A[id][1]/pw2[k+1];
        for(j=0;j<9;j++) {
            for(int v : M[k][INF*(x1+dx[j])+x2+dy[j]]) {
                //cout << k << ' ' << x1+dx[j] << ' ' << x2 + dy[j] << ' ' << v << '\n';
                if(ans[v]!=-1||inter(v, id)) {
                    if(ans[v]==-1) ans[v] = id;
                }
            }
        }
    }
    for(i=0;i<N;i++) cout << ans[i] + 1 << ' ';
}

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