답안 #153232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153232	2019-09-13T01:36:44 Z	username	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3000 ms	325160 KB

circle_selection

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define pb push_back
#define F first
#define S second
#define IOS cin.tie(0),ios_base::sync_with_stdio(false)
#define f2(x) (int64_t(x)*(x))
 
const int maxn=3e5+3,inf=2e9+3,bl=2e9+3;
struct C{int x,y,r,id;}a[maxn];
int n,res[maxn];
bitset<maxn>rmv;
unordered_map<int64_t,vector<int>>mp;
 
main(){
	IOS;
	cin>>n;
	REP(i,0,n)cin>>a[i].x>>a[i].y>>a[i].r,a[i].id=i;
	stable_sort(a,a+n,[](const C&x,const C&y){return 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,i,n)if(!rmv[j])mp[(int64_t)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[(int64_t)x*bl+y];
			for(auto it=tls.begin();it!=tls.end();++it){
				if(!rmv[*it]&&f2(a[i].x-a[*it].x)+f2(a[i].y-a[*it].y)<=f2(a[i].r+a[*it].r)){
					res[a[*it].id]=a[i].id;
					rmv[*it]=1;
				}
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

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

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	380 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	476 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	6 ms	632 KB	Output is correct
20	Correct	6 ms	632 KB	Output is correct
21	Correct	6 ms	708 KB	Output is correct
22	Correct	28 ms	4692 KB	Output is correct
23	Correct	27 ms	4616 KB	Output is correct
24	Correct	30 ms	4616 KB	Output is correct
25	Correct	27 ms	4740 KB	Output is correct
26	Correct	28 ms	4744 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	202 ms	18308 KB	Output is correct
2	Correct	205 ms	17248 KB	Output is correct
3	Correct	201 ms	16832 KB	Output is correct
4	Correct	199 ms	18320 KB	Output is correct
5	Correct	221 ms	16672 KB	Output is correct
6	Correct	1044 ms	66320 KB	Output is correct
7	Correct	268 ms	20204 KB	Output is correct
8	Correct	416 ms	27632 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	1241 ms	83152 KB	Output is correct
3	Execution timed out	3026 ms	286844 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3035 ms	325160 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	380 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	476 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	6 ms	632 KB	Output is correct
20	Correct	6 ms	632 KB	Output is correct
21	Correct	6 ms	708 KB	Output is correct
22	Correct	28 ms	4692 KB	Output is correct
23	Correct	27 ms	4616 KB	Output is correct
24	Correct	30 ms	4616 KB	Output is correct
25	Correct	27 ms	4740 KB	Output is correct
26	Correct	28 ms	4744 KB	Output is correct
27	Correct	9 ms	924 KB	Output is correct
28	Correct	9 ms	924 KB	Output is correct
29	Correct	9 ms	924 KB	Output is correct
30	Correct	61 ms	9052 KB	Output is correct
31	Correct	71 ms	9016 KB	Output is correct
32	Correct	63 ms	9056 KB	Output is correct
33	Correct	74 ms	6744 KB	Output is correct
34	Correct	74 ms	6908 KB	Output is correct
35	Correct	77 ms	6616 KB	Output is correct
36	Correct	1092 ms	84452 KB	Output is correct
37	Correct	1108 ms	84144 KB	Output is correct
38	Correct	1127 ms	84020 KB	Output is correct
39	Correct	410 ms	24920 KB	Output is correct
40	Correct	390 ms	24968 KB	Output is correct
41	Correct	386 ms	25000 KB	Output is correct
42	Correct	178 ms	13532 KB	Output is correct
43	Correct	1291 ms	139940 KB	Output is correct
44	Correct	1276 ms	140128 KB	Output is correct
45	Correct	1524 ms	140040 KB	Output is correct
46	Correct	1344 ms	140148 KB	Output is correct
47	Correct	1432 ms	140236 KB	Output is correct
48	Correct	1315 ms	140236 KB	Output is correct
49	Correct	1896 ms	140264 KB	Output is correct
50	Correct	1434 ms	140112 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	380 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	476 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	6 ms	632 KB	Output is correct
20	Correct	6 ms	632 KB	Output is correct
21	Correct	6 ms	708 KB	Output is correct
22	Correct	28 ms	4692 KB	Output is correct
23	Correct	27 ms	4616 KB	Output is correct
24	Correct	30 ms	4616 KB	Output is correct
25	Correct	27 ms	4740 KB	Output is correct
26	Correct	28 ms	4744 KB	Output is correct
27	Correct	202 ms	18308 KB	Output is correct
28	Correct	205 ms	17248 KB	Output is correct
29	Correct	201 ms	16832 KB	Output is correct
30	Correct	199 ms	18320 KB	Output is correct
31	Correct	221 ms	16672 KB	Output is correct
32	Correct	1044 ms	66320 KB	Output is correct
33	Correct	268 ms	20204 KB	Output is correct
34	Correct	416 ms	27632 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	1241 ms	83152 KB	Output is correct
37	Execution timed out	3026 ms	286844 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #153232

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