Submission #498490

#	Time	Username	Problem	Language	Result	Execution time	Memory
498490		Kipras	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3099 ms	47072 KiB

circle_selection

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const int maxN = 3*1e5+1;

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

ll square(ll a){
    return a*a;
}

int main()
{

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

    while(!a.empty()){
        pair<ll, pair<ll, pair<ll, ll>>> temp = (*a.begin());
        ll 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<ll, pair<ll, pair<ll, ll>>>> removeList;
        for(auto x : a){
            if(square(abs(x.second.second.first-posX))+square(abs(x.second.second.second-posY))<=square((r*-1)+(x.first*-1)))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: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13