답안 #106539

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

circle_selection

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define int int64_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 IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define f2(x) ((x)*(x))

const int maxn=3e5+9,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,VI>mp;
 
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=1ll<<31;
	REP(i,0,n){
		if(rmv[i])continue;
		while(a[i].r<(k>>1)){
			k>>=1;
			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])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:20: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	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	300 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	356 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	6 ms	640 KB	Output is correct
20	Correct	6 ms	768 KB	Output is correct
21	Correct	7 ms	640 KB	Output is correct
22	Correct	32 ms	4528 KB	Output is correct
23	Correct	33 ms	4520 KB	Output is correct
24	Correct	34 ms	3248 KB	Output is correct
25	Correct	37 ms	3632 KB	Output is correct
26	Correct	34 ms	4520 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	192 ms	18652 KB	Output is correct
2	Correct	203 ms	18408 KB	Output is correct
3	Correct	202 ms	17900 KB	Output is correct
4	Correct	169 ms	14564 KB	Output is correct
5	Correct	639 ms	19064 KB	Output is correct
6	Correct	1935 ms	55220 KB	Output is correct
7	Correct	628 ms	20644 KB	Output is correct
8	Correct	768 ms	28016 KB	Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	300 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	356 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	6 ms	640 KB	Output is correct
20	Correct	6 ms	768 KB	Output is correct
21	Correct	7 ms	640 KB	Output is correct
22	Correct	32 ms	4528 KB	Output is correct
23	Correct	33 ms	4520 KB	Output is correct
24	Correct	34 ms	3248 KB	Output is correct
25	Correct	37 ms	3632 KB	Output is correct
26	Correct	34 ms	4520 KB	Output is correct
27	Correct	10 ms	992 KB	Output is correct
28	Correct	10 ms	988 KB	Output is correct
29	Correct	7 ms	940 KB	Output is correct
30	Correct	99 ms	8728 KB	Output is correct
31	Correct	106 ms	8716 KB	Output is correct
32	Correct	110 ms	6324 KB	Output is correct
33	Correct	74 ms	5972 KB	Output is correct
34	Correct	78 ms	5872 KB	Output is correct
35	Correct	75 ms	6336 KB	Output is correct
36	Correct	1926 ms	75812 KB	Output is correct
37	Correct	1857 ms	71068 KB	Output is correct
38	Correct	1801 ms	76644 KB	Output is correct
39	Correct	603 ms	11668 KB	Output is correct
40	Correct	483 ms	11504 KB	Output is correct
41	Correct	543 ms	11604 KB	Output is correct
42	Correct	345 ms	10680 KB	Output is correct
43	Correct	2125 ms	139032 KB	Output is correct
44	Correct	2179 ms	139320 KB	Output is correct
45	Correct	2155 ms	139432 KB	Output is correct
46	Correct	2320 ms	139416 KB	Output is correct
47	Correct	2162 ms	139536 KB	Output is correct
48	Correct	2048 ms	139468 KB	Output is correct
49	Correct	2698 ms	139388 KB	Output is correct
50	Correct	2339 ms	139272 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	300 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	356 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	6 ms	640 KB	Output is correct
20	Correct	6 ms	768 KB	Output is correct
21	Correct	7 ms	640 KB	Output is correct
22	Correct	32 ms	4528 KB	Output is correct
23	Correct	33 ms	4520 KB	Output is correct
24	Correct	34 ms	3248 KB	Output is correct
25	Correct	37 ms	3632 KB	Output is correct
26	Correct	34 ms	4520 KB	Output is correct
27	Correct	192 ms	18652 KB	Output is correct
28	Correct	203 ms	18408 KB	Output is correct
29	Correct	202 ms	17900 KB	Output is correct
30	Correct	169 ms	14564 KB	Output is correct
31	Correct	639 ms	19064 KB	Output is correct
32	Correct	1935 ms	55220 KB	Output is correct
33	Correct	628 ms	20644 KB	Output is correct
34	Correct	768 ms	28016 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	1742 ms	71492 KB	Output is correct
37	Execution timed out	3057 ms	151324 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #106539

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