#include "bits/stdc++.h"
#define MAXN 300009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
pair<PII,PII>arr[MAXN];
bool cmp(pair<PII,PII>x,pair<PII,PII>y){
if(x.ff.ff!=y.ff.ff)
return (x.ff.ff>y.ff.ff);
return (x.ff.ss<y.ff.ss);
}
int ans[MAXN],id[MAXN];
ll sqr(int x){
return x*1LL*x;
}
ll dis(PII x,PII y){
return sqr(x.ff-y.ff)+sqr(x.ss-y.ss);
}
set<PII>s;
map<int,int>pm;
vector<PII>adj[MAXN];
int main(){
//~ freopen("file.in", "r", stdin);
int n,all=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y,r;
scanf("%d%d%d",&x,&y,&r);
arr[i]=mp(mp(r,i),mp(x,y));
if(i>1)
assert(r==arr[1].ff.ff);
s.insert(mp(x-r,i));
all+=(!y);
s.insert(mp(x+r,i));
}
sort(arr+1,arr+n+1,cmp);
if(n<=5000 and 1==0){//1st subtask
for(int i=1;i<=n;i++){
if(ans[arr[i].ff.ss])
continue;
for(int j=i;j<=n;j++)
if(!ans[arr[j].ff.ss] and dis(arr[i].ss,arr[j].ss)<=sqr(arr[i].ff.ff+arr[j].ff.ff))
ans[arr[j].ff.ss]=arr[i].ff.ss;
}
}
else if(all==n and 1==0){//2nd subtask
for(int i=1;i<=n;i++){
int x=arr[i].ss.ff;
int r=arr[i].ff.ff;
int ind=arr[i].ff.ss;
if(ans[ind])
continue;
ans[ind]=ind;
s.erase(mp(x+r,ind));
s.erase(mp(x-r,ind));
__typeof((s).begin())it=s.lower_bound(mp(x-r,-1));
while(it!=s.end()){
if(abs(it->ff-x)>r)
break;
if(!ans[it->ss])
ans[it->ss]=ind;
s.erase(it++);
}
}
}
else if(arr[1].ff.ff==arr[n].ff.ff){//3rd subtask
int r=arr[1].ff.ff;
for(int i=1;i<=n;i++)
pm[arr[i].ss.ff/r]=1;
int c=0;
tr(it,pm){
it->ss=++c;
id[c]=it->ff;
}
for(int i=1;i<=n;i++)
adj[pm[arr[i].ss.ff/r]].pb(mp(arr[i].ss.ss/r,arr[i].ff.ss));
for(int i=1;i<=c;i++)
sort(all(adj[i]));
for(int i=1;i<=n;i++){
int x=arr[i].ss.ff;
int y=arr[i].ss.ss;
int ind=arr[i].ff.ss;
if(ans[ind])
continue;
for(int j=max(1,pm[x/r]-2);j<=min(c,pm[x/r]+2);j++){
if(abs(id[j]-x/r)>2)
continue;
int pos=lower_bound(all(adj[j]),mp(y/r-2,-1))-adj[j].begin();
while(pos<int(adj[j].size()) and adj[j][pos].ff<=y/r+2){
int new_ind=adj[j][pos].ss;
if(!ans[new_ind] and dis(arr[ind].ss,arr[new_ind].ss)<=sqr(2*r))
ans[new_ind]=ind;
pos++;
}
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);;
puts("");
return 0;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
circle_selection.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&r);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
7348 KB |
Output is correct |
| 2 |
Runtime error |
16 ms |
14692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
14848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
14876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1806 ms |
59760 KB |
Output is correct |
| 2 |
Correct |
2001 ms |
75472 KB |
Output is correct |
| 3 |
Correct |
1098 ms |
75472 KB |
Output is correct |
| 4 |
Correct |
2017 ms |
75472 KB |
Output is correct |
| 5 |
Correct |
1750 ms |
75472 KB |
Output is correct |
| 6 |
Correct |
1012 ms |
75472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
7348 KB |
Output is correct |
| 2 |
Runtime error |
16 ms |
14692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
7348 KB |
Output is correct |
| 2 |
Runtime error |
16 ms |
14692 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
