Submission #1190742

#TimeUsernameProblemLanguageResultExecution timeMemory
1190742MalixCircle selection (APIO18_circle_selection)C++20
0 / 100
320 ms33320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,ll,ll> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; vector<ti> a; bool check(int x,int y){ ll x1=get<0>(a[x]); ll y1=get<1>(a[x]); ll z1=get<2>(a[x]); ll x2=get<0>(a[y]); ll y2=get<1>(a[y]); ll z2=get<2>(a[y]); return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(z1+z2)*(z1+z2)); } int main() { // ios::sync_with_stdio(0); // cin.tie(0); int n;cin>>n; a.resize(n); REP(i,0,n){ ll x,y,z;cin>>x>>y>>z; a[i]={x,y,z}; } sort(a.begin(),a.end()); set<pair<ll,int>> st; priority_queue<pair<ll,int>> pq; vi ans(n); REP(i,0,n)ans[i]=i; REP(i,0,n){ ll x=get<0>(a[i]); ll y=get<1>(a[i]); ll z=get<2>(a[i]); while(!pq.empty()&&pq.top().F<x-z){ st.erase({get<1>(a[pq.top().S]),pq.top().S}); pq.pop(); } auto it=st.lower_bound({y,-1}); int ps=it->S; if(check(i,ps)){ if(get<2>(a[i])>get<2>(a[ps]))ans[ps]=i; else if(get<2>(a[i])<get<2>(a[ps]))ans[i]=ps; else if(i<ps)ans[ps]=i; else ans[i]=ps; } if(it==st.begin()){ st.insert({y,i}); pq.push({x+z,i}); continue; } it--; ps=it->S; if(check(i,ps)){ if(get<2>(a[i])>get<2>(a[ps]))ans[ps]=i; else if(get<2>(a[i])<get<2>(a[ps]))ans[i]=ps; else if(i<ps)ans[ps]=i; else ans[i]=ps; } st.insert({y,i}); pq.push({x+z,i}); } REP(i,0,n)cout<<ans[i]+1<<" "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...