Submission #567241

#	Time	Username	Problem	Language	Result	Execution time	Memory
567241		Mahdi	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3098 ms	16160 KiB

circle_selection

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll>pil;
const int N=3e5+5;
int n, ans[N], x[N], y[N], r[N];
pii a[N];

bool cmp(const pii &h, const pii &f){
    if(h.F!=f.F)
        return h.F>f.F;
    return h.S<f.S;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x[i]>>y[i]>>r[i];
        a[i]={r[i], i};
    }
    sort(a, a+n, cmp);
    vector<int>v;
    ans[a[0].S]=a[0].S;
    v.push_back(a[0].S);
    for(int i=1;i<n;++i){
        int j=a[i].S;
        ans[j]=j;
        for(int k=0;k<v.size();++k){
            ll h=x[j]-x[v[k]];
            ll f=y[j]-y[v[k]];
            ll z=r[j]+r[v[k]];
            h*=h;
            f*=f;
            z*=z;
            if(h+f<=z){
                ans[j]=v[k];
                break;
            }
        }
        if(ans[j]==j)
            v.push_back(j);
    }
    for(int i=0;i<n;++i)
        cout<<ans[i]+1<<' ';
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int k=0;k<v.size();++k){
      |                     ~^~~~~~~~~

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