Submission #1190777

#TimeUsernameProblemLanguageResultExecution timeMemory
1190777MalixCircle selection (APIO18_circle_selection)C++20
0 / 100
343 ms15408 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,int> 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; set<pair<ll,int>> st; vi ans; 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]); int p=get<3>(a[x]); int q=get<3>(a[y]); if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(z1+z2)*(z1+z2)){ if(get<2>(a[x])>get<2>(a[y]))ans[q]=p; else if(get<2>(a[x])<get<2>(a[y]))ans[p]=q; else if(p<q)ans[q]=p; else ans[p]=q; return 1; } return 0; } void rem(auto it){ if(it==st.begin()||next(it)==st.end()){ st.erase(it); return; } auto it2=prev(it); auto it3=next(it); st.erase(it); int x=it2->S,y=it3->S; if(check(x,y)){ st.erase(it2); rem(it3); } } int main() { // ios::sync_with_stdio(0); // cin.tie(0); int n;cin>>n; a.resize(n); ll mx=0; REP(i,0,n){ ll x,y,z;cin>>x>>y>>z; a[i]={x,y,z,i}; mx=max(mx,z); } sort(a.begin(),a.end()); priority_queue<pair<ll,int>> pq; ans.resize(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-mx){ pq.pop(); if(st.count({get<1>(a[pq.top().S]),pq.top().S})==0)continue; auto it=st.find({get<1>(a[pq.top().S]),pq.top().S}); rem(it); } if(pq.empty()){ st.insert({y,i}); pq.push({x+z,i}); continue; } auto it=st.lower_bound({y,-1}); int ps; if(it!=st.end()){ ps=it->S; if(check(i,ps)){ rem(it); continue; } } if(it!=st.begin()){ it--; ps=it->S; if(check(i,ps)){ rem(it); continue; } } 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...