oj.uz

Submission #498486

# Submission time Handle Problem Language Result Execution time Memory
498486 2021-12-25T10:00:25 Z Kipras Circle selection (APIO18_circle_selection) C++14
0 / 100
 694 ms 32208 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+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.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 537 ms 31988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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