Submission #1313219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313219		jahongir	Circle selection (APIO18_circle_selection)	C++20	0 / 100	3115 ms	580584 KiB

circle_selection

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


bool check(const array<int,3> &a, const array<int,3> &b){
    ll dx = a[0]-b[0], dy = a[1]-b[1], r = a[2]+b[2];
    return dx*dx + dy*dy <= r*r;
}


void solve(){
    int n; cin >> n;

    vector<array<int,3>> vec(n);
    map<ll,set<int>> mp;
    int cnt = 0;
    for(auto &[x,y,r] : vec){
        cin >> x >> y >> r;
        mp[(x/r) + ((y/r)<<30)].insert(cnt++);
    }

    vector<int> ind(n);
    iota(all(ind),0);


    sort(all(ind),[&](const int &i, const int &j){
        if(vec[i][2]==vec[j][2]) return i < j;
        return vec[i][2] > vec[j][2];
    });

    vector<int> res(n,-1);
    int r = vec[ind[0]][2];

    int lim = 2;

    for(int i = 0; i < n; i++) if(res[ind[i]]==-1){
        int x = vec[ind[i]][0], y = vec[ind[i]][1];
        for(int dx = -lim; dx <= lim; dx++)
            for(int dy = -lim; dy <= lim; dy++){
                vector<int> rem;
                for(auto j : mp[(x/r+dx)+((y/r+dy)<<30)]){
                    if(check(vec[ind[i]],vec[j])){
                        rem.emplace_back(j);
                        res[j] = ind[i];
                    }
                }
                for(auto j : rem)
                    mp[(x/r+dx)+((y/r+dy)<<30)].erase(j);
            }
    }

    for(auto x : res) cout << x+1 << ' ';
}



signed main(){
    cin.tie(0)->sync_with_stdio(0);


    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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