Submission #49264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49264	2018-05-24T15:24:11 Z	Kerim	Circle selection (APIO18_circle_selection)	C++17	42 / 100	2019 ms	86608 KB

circle_selection

#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=pm[x/r]-2;j<=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);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7288 KB	Output is correct
2	Correct	8 ms	7524 KB	Output is correct
3	Correct	8 ms	7524 KB	Output is correct
4	Correct	8 ms	7524 KB	Output is correct
5	Correct	8 ms	7524 KB	Output is correct
6	Correct	9 ms	7524 KB	Output is correct
7	Correct	9 ms	7524 KB	Output is correct
8	Correct	9 ms	7524 KB	Output is correct
9	Correct	8 ms	7524 KB	Output is correct
10	Correct	8 ms	7556 KB	Output is correct
11	Correct	10 ms	7760 KB	Output is correct
12	Correct	8 ms	7760 KB	Output is correct
13	Correct	9 ms	7760 KB	Output is correct
14	Correct	8 ms	7760 KB	Output is correct
15	Correct	7 ms	7760 KB	Output is correct
16	Correct	10 ms	7760 KB	Output is correct
17	Correct	9 ms	7760 KB	Output is correct
18	Correct	10 ms	7788 KB	Output is correct
19	Correct	18 ms	8172 KB	Output is correct
20	Correct	16 ms	8172 KB	Output is correct
21	Correct	16 ms	8188 KB	Output is correct
22	Correct	65 ms	8332 KB	Output is correct
23	Correct	53 ms	8332 KB	Output is correct
24	Correct	71 ms	8332 KB	Output is correct
25	Correct	59 ms	8476 KB	Output is correct
26	Correct	53 ms	8476 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1000 ms	43792 KB	Output is correct
2	Correct	1083 ms	43844 KB	Output is correct
3	Correct	1042 ms	43844 KB	Output is correct
4	Correct	987 ms	43852 KB	Output is correct
5	Correct	992 ms	43852 KB	Output is correct
6	Correct	940 ms	43852 KB	Output is correct
7	Correct	962 ms	43852 KB	Output is correct
8	Correct	851 ms	43852 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	43852 KB	Output is correct
2	Runtime error	298 ms	43852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1829 ms	70720 KB	Output is correct
2	Correct	2019 ms	86608 KB	Output is correct
3	Correct	914 ms	86608 KB	Output is correct
4	Correct	1531 ms	86608 KB	Output is correct
5	Correct	1629 ms	86608 KB	Output is correct
6	Correct	1238 ms	86608 KB	Output is correct

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7288 KB	Output is correct
2	Correct	8 ms	7524 KB	Output is correct
3	Correct	8 ms	7524 KB	Output is correct
4	Correct	8 ms	7524 KB	Output is correct
5	Correct	8 ms	7524 KB	Output is correct
6	Correct	9 ms	7524 KB	Output is correct
7	Correct	9 ms	7524 KB	Output is correct
8	Correct	9 ms	7524 KB	Output is correct
9	Correct	8 ms	7524 KB	Output is correct
10	Correct	8 ms	7556 KB	Output is correct
11	Correct	10 ms	7760 KB	Output is correct
12	Correct	8 ms	7760 KB	Output is correct
13	Correct	9 ms	7760 KB	Output is correct
14	Correct	8 ms	7760 KB	Output is correct
15	Correct	7 ms	7760 KB	Output is correct
16	Correct	10 ms	7760 KB	Output is correct
17	Correct	9 ms	7760 KB	Output is correct
18	Correct	10 ms	7788 KB	Output is correct
19	Correct	18 ms	8172 KB	Output is correct
20	Correct	16 ms	8172 KB	Output is correct
21	Correct	16 ms	8188 KB	Output is correct
22	Correct	65 ms	8332 KB	Output is correct
23	Correct	53 ms	8332 KB	Output is correct
24	Correct	71 ms	8332 KB	Output is correct
25	Correct	59 ms	8476 KB	Output is correct
26	Correct	53 ms	8476 KB	Output is correct
27	Runtime error	34 ms	86608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7288 KB	Output is correct
2	Correct	8 ms	7524 KB	Output is correct
3	Correct	8 ms	7524 KB	Output is correct
4	Correct	8 ms	7524 KB	Output is correct
5	Correct	8 ms	7524 KB	Output is correct
6	Correct	9 ms	7524 KB	Output is correct
7	Correct	9 ms	7524 KB	Output is correct
8	Correct	9 ms	7524 KB	Output is correct
9	Correct	8 ms	7524 KB	Output is correct
10	Correct	8 ms	7556 KB	Output is correct
11	Correct	10 ms	7760 KB	Output is correct
12	Correct	8 ms	7760 KB	Output is correct
13	Correct	9 ms	7760 KB	Output is correct
14	Correct	8 ms	7760 KB	Output is correct
15	Correct	7 ms	7760 KB	Output is correct
16	Correct	10 ms	7760 KB	Output is correct
17	Correct	9 ms	7760 KB	Output is correct
18	Correct	10 ms	7788 KB	Output is correct
19	Correct	18 ms	8172 KB	Output is correct
20	Correct	16 ms	8172 KB	Output is correct
21	Correct	16 ms	8188 KB	Output is correct
22	Correct	65 ms	8332 KB	Output is correct
23	Correct	53 ms	8332 KB	Output is correct
24	Correct	71 ms	8332 KB	Output is correct
25	Correct	59 ms	8476 KB	Output is correct
26	Correct	53 ms	8476 KB	Output is correct
27	Correct	1000 ms	43792 KB	Output is correct
28	Correct	1083 ms	43844 KB	Output is correct
29	Correct	1042 ms	43844 KB	Output is correct
30	Correct	987 ms	43852 KB	Output is correct
31	Correct	992 ms	43852 KB	Output is correct
32	Correct	940 ms	43852 KB	Output is correct
33	Correct	962 ms	43852 KB	Output is correct
34	Correct	851 ms	43852 KB	Output is correct
35	Correct	10 ms	43852 KB	Output is correct
36	Runtime error	298 ms	43852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Halted	0 ms	0 KB	-