Submission #106530

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106530	2019-04-19T02:59:43 Z	username	Circle selection (APIO18_circle_selection)	C++14	49 / 100	3000 ms	286228 KB

circle_selection

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define int int64_t//int_fast64_t
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define pb emplace_back
#define F first
#define S second
#define endl '\n'
//																#define __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
#define f2(x) ((x)*(x))
const int maxn=3e5+9,inf=1ll<<60,bl=3e9;
struct C{int x,y,r,id;}a[maxn];
int n,rmv[maxn],res[maxn];
unordered_map<int,VI>mp;
list<int>ls;
 
main(){
	IOS;
	cin>>n;
	REP(i,0,n)cin>>a[i].x>>a[i].y>>a[i].r,a[i].id=i;
	sort(a,a+n,[](C x,C y){return x.r==y.r?x.id<y.id:x.r>y.r;});
	int k=inf;
	REP(i,0,n){
		if(rmv[i])continue;
		if(2*a[i].r<k){
			k=a[i].r;
			mp.clear();
			REP(j,0,n){
				if(!rmv[j]){
					mp[a[j].x/k*bl+a[j].y/k].pb(j);
				}
			}
		}
		int xx=a[i].x/k,yy=a[i].y/k;
		REP(x,xx-2,xx+3)REP(y,yy-2,yy+3){
			auto&tls=mp[x*bl+y];
			for(auto it=tls.begin();it!=tls.end();++it){
				if(rmv[*it])continue;
				C c=a[*it];
				if(f2(a[i].x-c.x)+f2(a[i].y-c.y)<=f2(a[i].r+c.r)){
					res[c.id]=a[i].id;
					rmv[*it]=1;
				}
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

circle_selection.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	428 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	3 ms	512 KB	Output is correct
15	Correct	3 ms	512 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	4 ms	804 KB	Output is correct
20	Correct	7 ms	768 KB	Output is correct
21	Correct	6 ms	768 KB	Output is correct
22	Correct	28 ms	4744 KB	Output is correct
23	Correct	37 ms	4624 KB	Output is correct
24	Correct	36 ms	4744 KB	Output is correct
25	Correct	34 ms	4740 KB	Output is correct
26	Correct	40 ms	4752 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	212 ms	16916 KB	Output is correct
2	Correct	201 ms	18016 KB	Output is correct
3	Correct	209 ms	18784 KB	Output is correct
4	Correct	230 ms	17000 KB	Output is correct
5	Correct	241 ms	21800 KB	Output is correct
6	Correct	1163 ms	70660 KB	Output is correct
7	Correct	363 ms	25208 KB	Output is correct
8	Correct	510 ms	32648 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1246 ms	83316 KB	Output is correct
3	Execution timed out	3070 ms	286228 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3027 ms	285008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	428 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	3 ms	512 KB	Output is correct
15	Correct	3 ms	512 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	4 ms	804 KB	Output is correct
20	Correct	7 ms	768 KB	Output is correct
21	Correct	6 ms	768 KB	Output is correct
22	Correct	28 ms	4744 KB	Output is correct
23	Correct	37 ms	4624 KB	Output is correct
24	Correct	36 ms	4744 KB	Output is correct
25	Correct	34 ms	4740 KB	Output is correct
26	Correct	40 ms	4752 KB	Output is correct
27	Correct	12 ms	1024 KB	Output is correct
28	Correct	12 ms	1024 KB	Output is correct
29	Correct	12 ms	1024 KB	Output is correct
30	Correct	90 ms	9016 KB	Output is correct
31	Correct	91 ms	9020 KB	Output is correct
32	Correct	118 ms	9020 KB	Output is correct
33	Correct	72 ms	6608 KB	Output is correct
34	Correct	64 ms	6768 KB	Output is correct
35	Correct	68 ms	6120 KB	Output is correct
36	Correct	1509 ms	84560 KB	Output is correct
37	Correct	1441 ms	84352 KB	Output is correct
38	Correct	1482 ms	84176 KB	Output is correct
39	Correct	557 ms	26812 KB	Output is correct
40	Correct	532 ms	26616 KB	Output is correct
41	Correct	552 ms	26612 KB	Output is correct
42	Correct	186 ms	14532 KB	Output is correct
43	Correct	1548 ms	140228 KB	Output is correct
44	Correct	1687 ms	140328 KB	Output is correct
45	Correct	1739 ms	140176 KB	Output is correct
46	Correct	1684 ms	140344 KB	Output is correct
47	Correct	1636 ms	140548 KB	Output is correct
48	Correct	1682 ms	140380 KB	Output is correct
49	Correct	1728 ms	140428 KB	Output is correct
50	Correct	1581 ms	140332 KB	Output is correct

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	428 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	3 ms	512 KB	Output is correct
15	Correct	3 ms	512 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	4 ms	804 KB	Output is correct
20	Correct	7 ms	768 KB	Output is correct
21	Correct	6 ms	768 KB	Output is correct
22	Correct	28 ms	4744 KB	Output is correct
23	Correct	37 ms	4624 KB	Output is correct
24	Correct	36 ms	4744 KB	Output is correct
25	Correct	34 ms	4740 KB	Output is correct
26	Correct	40 ms	4752 KB	Output is correct
27	Correct	212 ms	16916 KB	Output is correct
28	Correct	201 ms	18016 KB	Output is correct
29	Correct	209 ms	18784 KB	Output is correct
30	Correct	230 ms	17000 KB	Output is correct
31	Correct	241 ms	21800 KB	Output is correct
32	Correct	1163 ms	70660 KB	Output is correct
33	Correct	363 ms	25208 KB	Output is correct
34	Correct	510 ms	32648 KB	Output is correct
35	Correct	2 ms	384 KB	Output is correct
36	Correct	1246 ms	83316 KB	Output is correct
37	Execution timed out	3070 ms	286228 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

Submission #106530

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0