Submission #724233

#TimeUsernameProblemLanguageResultExecution timeMemory
724233n0sk1llCircle selection (APIO18_circle_selection)C++14
49 / 100
3085 ms658876 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow map<pii,set<pair<pii,pii>>> koji; int ans[300005]; int main() { FAST; int R=2e9+1; set<pair<pii,pii>> krugovi; int n; cin>>n; ff(i,0,n) { int x,y,r; cin>>x>>y>>r; krugovi.insert({{r,-i},{x,y}}); koji[{(x+1e9)/R,(y+1e9)/R}].insert({{r,-i},{x,y}}); } while (!krugovi.empty()) { auto it=*prev(krugovi.end()); int r=it.xx.xx,i=-it.xx.yy,x=it.yy.xx,y=it.yy.yy; if (2*r<=R) { while (2*r<=R) R/=2; koji.clear(); for (auto jt : krugovi) { int x1=jt.yy.xx,y1=jt.yy.yy; koji[{(x1+1e9)/R,(y1+1e9)/R}].insert(jt); } } vector<pair<pii,pii>> to_delete; fff(dx,-2,2) fff(dy,-2,2) for (auto jt : koji[{(x+1e9)/R+dx,(y+1e9)/R+dy}]) { int r1=jt.xx.xx,i1=-jt.xx.yy,x1=jt.yy.xx,y1=jt.yy.yy; if ((li)(r+r1)*(r+r1) >= (li)(x-x1)*(x-x1) + (li)(y-y1)*(y-y1)) ans[i1]=i,to_delete.pb({{r1,-i1},{x1,y1}}); } for (auto jt : to_delete) { krugovi.erase(jt); int x1=jt.yy.xx,y1=jt.yy.yy; koji[{(x1+1e9)/R,(y1+1e9)/R}].erase(jt); } } ff(i,0,n) cout<<ans[i]+1<<" "; } //Note to self: Check for overflow /* 3 1 1 1 2 2 2 3 3 3 */
#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...