Submission #498486

#	Time	Username	Problem	Language	Result	Execution time	Memory
498486		Kipras	Circle selection (APIO18_circle_selection)	C++14	0 / 100	694 ms	32208 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

const int maxN = 3*1e5+1;

int n;
//radius, index, pos.x, pos.y
set<pair<int, pair<int, pair<int, int>>>> a;
int removedBy[maxN];

long long square(int a){
    return a*a;
}

int main()
{

    cin>>n;
    for(int i = 1; i <= n; i++){
        int b, c, d;
        cin>>b>>c>>d;
        a.insert({-d, {i,{b, c}}});
    }

    while(!a.empty()){
        pair<int, pair<int, pair<int, int>>> temp = (*a.begin());
        int r=temp.first, ind=temp.second.first, posX=temp.second.second.first, posY=temp.second.second.second;
        a.erase(a.begin());
        removedBy[ind]=ind;
        vector<pair<int, pair<int, pair<int, int>>>> removeList;
        for(auto x : a){
            if(square(abs(x.second.second.first-posX))+square(abs(x.second.second.second-posY))<=square(r+x.first))removeList.push_back(x);
        }
        for(auto x : removeList){
            a.erase(a.find(x));
            removedBy[x.second.first]=ind;
        }
    }

    for(int i = 1; i <= n; i++){
        cout<<removedBy[i]<<" ";
    }

    return 0;
}

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