#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));
s.insert(mp(x-r,i));
all+=(!y);
s.insert(mp(x+r,i));
}
sort(arr+1,arr+n+1,cmp);
if(n<=5000){//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){//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++;
}
}
}
}
else
assert(0);
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 |
9 ms |
7380 KB |
Output is correct |
2 |
Correct |
9 ms |
7432 KB |
Output is correct |
3 |
Correct |
9 ms |
7592 KB |
Output is correct |
4 |
Correct |
9 ms |
7592 KB |
Output is correct |
5 |
Correct |
8 ms |
7592 KB |
Output is correct |
6 |
Correct |
9 ms |
7688 KB |
Output is correct |
7 |
Correct |
9 ms |
7688 KB |
Output is correct |
8 |
Correct |
8 ms |
7688 KB |
Output is correct |
9 |
Correct |
7 ms |
7688 KB |
Output is correct |
10 |
Correct |
8 ms |
7688 KB |
Output is correct |
11 |
Correct |
7 ms |
7688 KB |
Output is correct |
12 |
Correct |
7 ms |
7688 KB |
Output is correct |
13 |
Correct |
7 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7708 KB |
Output is correct |
15 |
Correct |
7 ms |
7708 KB |
Output is correct |
16 |
Correct |
8 ms |
7708 KB |
Output is correct |
17 |
Correct |
8 ms |
7708 KB |
Output is correct |
18 |
Correct |
8 ms |
7708 KB |
Output is correct |
19 |
Correct |
14 ms |
8164 KB |
Output is correct |
20 |
Correct |
14 ms |
8164 KB |
Output is correct |
21 |
Correct |
14 ms |
8180 KB |
Output is correct |
22 |
Correct |
47 ms |
8196 KB |
Output is correct |
23 |
Correct |
47 ms |
8196 KB |
Output is correct |
24 |
Correct |
47 ms |
8264 KB |
Output is correct |
25 |
Correct |
50 ms |
8264 KB |
Output is correct |
26 |
Correct |
47 ms |
8264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1181 ms |
43784 KB |
Output is correct |
2 |
Correct |
1018 ms |
43796 KB |
Output is correct |
3 |
Correct |
1058 ms |
43796 KB |
Output is correct |
4 |
Correct |
1012 ms |
43816 KB |
Output is correct |
5 |
Correct |
978 ms |
43816 KB |
Output is correct |
6 |
Correct |
894 ms |
43816 KB |
Output is correct |
7 |
Correct |
1094 ms |
43816 KB |
Output is correct |
8 |
Correct |
931 ms |
43816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
43816 KB |
Output is correct |
2 |
Runtime error |
275 ms |
43816 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 |
1984 ms |
70620 KB |
Output is correct |
2 |
Correct |
1699 ms |
86444 KB |
Output is correct |
3 |
Correct |
852 ms |
86444 KB |
Output is correct |
4 |
Correct |
1785 ms |
86444 KB |
Output is correct |
5 |
Correct |
2070 ms |
86444 KB |
Output is correct |
6 |
Correct |
1172 ms |
86444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7380 KB |
Output is correct |
2 |
Correct |
9 ms |
7432 KB |
Output is correct |
3 |
Correct |
9 ms |
7592 KB |
Output is correct |
4 |
Correct |
9 ms |
7592 KB |
Output is correct |
5 |
Correct |
8 ms |
7592 KB |
Output is correct |
6 |
Correct |
9 ms |
7688 KB |
Output is correct |
7 |
Correct |
9 ms |
7688 KB |
Output is correct |
8 |
Correct |
8 ms |
7688 KB |
Output is correct |
9 |
Correct |
7 ms |
7688 KB |
Output is correct |
10 |
Correct |
8 ms |
7688 KB |
Output is correct |
11 |
Correct |
7 ms |
7688 KB |
Output is correct |
12 |
Correct |
7 ms |
7688 KB |
Output is correct |
13 |
Correct |
7 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7708 KB |
Output is correct |
15 |
Correct |
7 ms |
7708 KB |
Output is correct |
16 |
Correct |
8 ms |
7708 KB |
Output is correct |
17 |
Correct |
8 ms |
7708 KB |
Output is correct |
18 |
Correct |
8 ms |
7708 KB |
Output is correct |
19 |
Correct |
14 ms |
8164 KB |
Output is correct |
20 |
Correct |
14 ms |
8164 KB |
Output is correct |
21 |
Correct |
14 ms |
8180 KB |
Output is correct |
22 |
Correct |
47 ms |
8196 KB |
Output is correct |
23 |
Correct |
47 ms |
8196 KB |
Output is correct |
24 |
Correct |
47 ms |
8264 KB |
Output is correct |
25 |
Correct |
50 ms |
8264 KB |
Output is correct |
26 |
Correct |
47 ms |
8264 KB |
Output is correct |
27 |
Runtime error |
33 ms |
86444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7380 KB |
Output is correct |
2 |
Correct |
9 ms |
7432 KB |
Output is correct |
3 |
Correct |
9 ms |
7592 KB |
Output is correct |
4 |
Correct |
9 ms |
7592 KB |
Output is correct |
5 |
Correct |
8 ms |
7592 KB |
Output is correct |
6 |
Correct |
9 ms |
7688 KB |
Output is correct |
7 |
Correct |
9 ms |
7688 KB |
Output is correct |
8 |
Correct |
8 ms |
7688 KB |
Output is correct |
9 |
Correct |
7 ms |
7688 KB |
Output is correct |
10 |
Correct |
8 ms |
7688 KB |
Output is correct |
11 |
Correct |
7 ms |
7688 KB |
Output is correct |
12 |
Correct |
7 ms |
7688 KB |
Output is correct |
13 |
Correct |
7 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7708 KB |
Output is correct |
15 |
Correct |
7 ms |
7708 KB |
Output is correct |
16 |
Correct |
8 ms |
7708 KB |
Output is correct |
17 |
Correct |
8 ms |
7708 KB |
Output is correct |
18 |
Correct |
8 ms |
7708 KB |
Output is correct |
19 |
Correct |
14 ms |
8164 KB |
Output is correct |
20 |
Correct |
14 ms |
8164 KB |
Output is correct |
21 |
Correct |
14 ms |
8180 KB |
Output is correct |
22 |
Correct |
47 ms |
8196 KB |
Output is correct |
23 |
Correct |
47 ms |
8196 KB |
Output is correct |
24 |
Correct |
47 ms |
8264 KB |
Output is correct |
25 |
Correct |
50 ms |
8264 KB |
Output is correct |
26 |
Correct |
47 ms |
8264 KB |
Output is correct |
27 |
Correct |
1181 ms |
43784 KB |
Output is correct |
28 |
Correct |
1018 ms |
43796 KB |
Output is correct |
29 |
Correct |
1058 ms |
43796 KB |
Output is correct |
30 |
Correct |
1012 ms |
43816 KB |
Output is correct |
31 |
Correct |
978 ms |
43816 KB |
Output is correct |
32 |
Correct |
894 ms |
43816 KB |
Output is correct |
33 |
Correct |
1094 ms |
43816 KB |
Output is correct |
34 |
Correct |
931 ms |
43816 KB |
Output is correct |
35 |
Correct |
7 ms |
43816 KB |
Output is correct |
36 |
Runtime error |
275 ms |
43816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
37 |
Halted |
0 ms |
0 KB |
- |