답안 #106547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106547	2019-04-19T03:31:23 Z	username	원 고르기 (APIO18_circle_selection)	C++14	19 / 100	3000 ms	284868 KB

circle_selection

#include<bits/stdc++.h>
#define int int64_t
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) ((x)*(x))

const int maxn=3e5+3,inf=1ll<<60,bl=2e9+3;
struct C{int x,y,r,id;}a[maxn];
int n,res[maxn];
bitset<maxn>rmv;
unordered_map<int,vector<int>>mp;
 
main(){
	IOS;
	cin>>n;
	int mnx=inf,mny=inf;
	REP(i,0,n)cin>>a[i].x>>a[i].y>>a[i].r,a[i].id=i,mnx=min(mnx,a[i].x),mny=min(mny,a[i].y);
	REP(i,0,n)a[i].x=a[i].x-mnx+1,a[i].y=a[i].y-mny+1;
	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,i,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]&&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:18: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	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	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	2 ms	384 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	384 KB	Output is correct
16	Correct	4 ms	512 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	5 ms	640 KB	Output is correct
20	Correct	6 ms	640 KB	Output is correct
21	Correct	6 ms	640 KB	Output is correct
22	Correct	37 ms	4624 KB	Output is correct
23	Correct	24 ms	4624 KB	Output is correct
24	Correct	51 ms	4624 KB	Output is correct
25	Correct	36 ms	4680 KB	Output is correct
26	Correct	37 ms	4624 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	187 ms	15952 KB	Output is correct
2	Correct	217 ms	14644 KB	Output is correct
3	Correct	190 ms	16600 KB	Output is correct
4	Correct	202 ms	15620 KB	Output is correct
5	Correct	284 ms	19700 KB	Output is correct
6	Correct	1344 ms	68364 KB	Output is correct
7	Correct	367 ms	22908 KB	Output is correct
8	Correct	554 ms	28724 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1551 ms	82464 KB	Output is correct
3	Execution timed out	3035 ms	284868 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	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	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	2 ms	384 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	384 KB	Output is correct
16	Correct	4 ms	512 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	5 ms	640 KB	Output is correct
20	Correct	6 ms	640 KB	Output is correct
21	Correct	6 ms	640 KB	Output is correct
22	Correct	37 ms	4624 KB	Output is correct
23	Correct	24 ms	4624 KB	Output is correct
24	Correct	51 ms	4624 KB	Output is correct
25	Correct	36 ms	4680 KB	Output is correct
26	Correct	37 ms	4624 KB	Output is correct
27	Correct	9 ms	984 KB	Output is correct
28	Correct	9 ms	1024 KB	Output is correct
29	Correct	11 ms	944 KB	Output is correct
30	Correct	91 ms	9020 KB	Output is correct
31	Correct	109 ms	8892 KB	Output is correct
32	Correct	99 ms	8980 KB	Output is correct
33	Correct	79 ms	5744 KB	Output is correct
34	Correct	93 ms	5932 KB	Output is correct
35	Correct	70 ms	5360 KB	Output is correct
36	Correct	1497 ms	83664 KB	Output is correct
37	Correct	1489 ms	83688 KB	Output is correct
38	Correct	1575 ms	83556 KB	Output is correct
39	Correct	556 ms	25820 KB	Output is correct
40	Correct	563 ms	25856 KB	Output is correct
41	Correct	516 ms	25996 KB	Output is correct
42	Correct	284 ms	13832 KB	Output is correct
43	Correct	1661 ms	139464 KB	Output is correct
44	Correct	1712 ms	139460 KB	Output is correct
45	Correct	1716 ms	139316 KB	Output is correct
46	Correct	1669 ms	139460 KB	Output is correct
47	Correct	1727 ms	139588 KB	Output is correct
48	Correct	1689 ms	139816 KB	Output is correct
49	Execution timed out	3039 ms	139512 KB	Time limit exceeded
50	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	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	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	2 ms	384 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	384 KB	Output is correct
16	Correct	4 ms	512 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	5 ms	640 KB	Output is correct
20	Correct	6 ms	640 KB	Output is correct
21	Correct	6 ms	640 KB	Output is correct
22	Correct	37 ms	4624 KB	Output is correct
23	Correct	24 ms	4624 KB	Output is correct
24	Correct	51 ms	4624 KB	Output is correct
25	Correct	36 ms	4680 KB	Output is correct
26	Correct	37 ms	4624 KB	Output is correct
27	Correct	187 ms	15952 KB	Output is correct
28	Correct	217 ms	14644 KB	Output is correct
29	Correct	190 ms	16600 KB	Output is correct
30	Correct	202 ms	15620 KB	Output is correct
31	Correct	284 ms	19700 KB	Output is correct
32	Correct	1344 ms	68364 KB	Output is correct
33	Correct	367 ms	22908 KB	Output is correct
34	Correct	554 ms	28724 KB	Output is correct
35	Correct	2 ms	384 KB	Output is correct
36	Correct	1551 ms	82464 KB	Output is correct
37	Execution timed out	3035 ms	284868 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #106547

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 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
0 / 30.0

Subtask #6
0 / 13.0