oj.uz

Submission #498487

# Submission time Handle Problem Language Result Execution time Memory
498487 2021-12-25T10:02:26 Z Kipras Circle selection (APIO18_circle_selection) C++14
0 / 100
 648 ms 25512 KB 
#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*-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
0 / 7.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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