oj.uz

Submission #51063

# Submission time Handle Problem Language Result Execution time Memory
51063 2018-06-16T02:11:14 Z edisonhello Circle selection (APIO18_circle_selection) C++11
0 / 100
 2238 ms 41888 KB 
#include<bits/stdc++.h>
using namespace std;

int n,pos[300005],ans[300005];
struct circle{
    int x,y,r,i;
} c[300005];

namespace std {
    template<> struct hash<pair<int,int>> {
        long long operator()(const pair<int,int> &a) const {
            return a.first*1000000009+a.second;
        }
    };
}

unordered_map<pair<int,int>,int> mp;
vector<int> idxs[300005];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>c[i].x>>c[i].y>>c[i].r;
        c[i].i=i+1;
    }
    sort(c,c+n,[](const circle &a,const circle &b){ return a.r==b.r?a.i<b.i:a.r>b.r; });
    // for(int i=0;i<n;++i)pos[c[i].i]=i;
    int masterPtr=0;
    int D=c[0].r,killcount=0;

    auto buildGraph=[&](){
        for(int i=1;i<=int(mp.size());++i)idxs[i].clear();
        mp.clear();
        D=c[masterPtr].r;
        killcount=0;
        for(int i=masterPtr;i<n;++i){
            pair<int,int> pos(c[i].x/D,c[i].y/D);
            int &it=mp[pos];
            if(it)idxs[it].push_back(i);
            else idxs[(it=mp.size())].push_back(i);
        }
    };

    buildGraph();
    while(masterPtr<n){
        while(masterPtr<n && c[masterPtr].i==0)++masterPtr;
        if(masterPtr>=n)break;
        // cout<<"now masterPtr: "<<masterPtr<<" circle is "<<c[masterPtr].i<<endl;
        // cout<<"circle position: "<<c[masterPtr].x<<" "<<c[masterPtr].y<<endl;
        if(D/c[masterPtr].r>=100 || killcount>=8000){
            buildGraph();
        }
        pair<int,int> pos(c[masterPtr].x/D,c[masterPtr].y/D);
        for(int dx=-2;dx<=2;++dx){
            for(int dy=-2;dy<=2;++dy){
                auto it=mp.find(make_pair(pos.first+dx,pos.second+dy));
                if(it==mp.end())continue;
                for(int i:idxs[it->second]){
                    if(c[i].i==0)continue;
                    if(1ll*(c[i].x-c[masterPtr].x)*(c[i].x-c[masterPtr].x)+1ll*(c[i].y-c[masterPtr].y)*(c[i].y-c[masterPtr].y)>1ll*(c[masterPtr].r+c[i].r)*(c[masterPtr].r+c[i].r))continue;
                    ans[c[i].i]=c[masterPtr].i;
                    // cout<<"killed "<<c[i].i<<", killer: "<<c[masterPtr].i<<endl;
                    
                    if(c[i].i!=c[masterPtr].i)c[i].i=0;
                    ++killcount;
                }
            }
        }
        c[masterPtr].i=0;
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Incorrect 7 ms 7544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 17000 KB Output is correct
2 Incorrect 259 ms 17320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 17320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2238 ms 41888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Incorrect 7 ms 7544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7544 KB Output is correct
2 Incorrect 7 ms 7544 KB Output isn't correct
3 Halted 0 ms 0 KB -