답안 #106520

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

circle_selection

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define MST(a,v) memset(a,(v),sizeof a)
#define pb push_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,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;
	sort(a,a+n,[](C x,C y){return x.r==y.r?x.id<y.id:x.r>y.r;});
	MST(rmv,0);
	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 end=mp[x*bl+y].end();
			for(auto it=mp[x*bl+y].begin();it!=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;
//					mp[x*bl+y].erase(it++);
				}
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

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

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2688 KB	Output is correct
2	Correct	3 ms	2688 KB	Output is correct
3	Correct	4 ms	2688 KB	Output is correct
4	Correct	5 ms	2560 KB	Output is correct
5	Correct	4 ms	2688 KB	Output is correct
6	Correct	4 ms	2688 KB	Output is correct
7	Correct	4 ms	2688 KB	Output is correct
8	Correct	5 ms	2688 KB	Output is correct
9	Correct	5 ms	2688 KB	Output is correct
10	Correct	4 ms	2688 KB	Output is correct
11	Correct	6 ms	2820 KB	Output is correct
12	Correct	5 ms	2816 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	5 ms	2816 KB	Output is correct
15	Correct	5 ms	2816 KB	Output is correct
16	Correct	4 ms	2816 KB	Output is correct
17	Correct	5 ms	2688 KB	Output is correct
18	Correct	6 ms	2688 KB	Output is correct
19	Correct	7 ms	3044 KB	Output is correct
20	Correct	8 ms	3072 KB	Output is correct
21	Correct	8 ms	2944 KB	Output is correct
22	Correct	34 ms	6928 KB	Output is correct
23	Correct	41 ms	6896 KB	Output is correct
24	Correct	50 ms	7048 KB	Output is correct
25	Correct	50 ms	7048 KB	Output is correct
26	Correct	55 ms	7176 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	214 ms	16868 KB	Output is correct
2	Correct	215 ms	17892 KB	Output is correct
3	Correct	191 ms	18908 KB	Output is correct
4	Correct	206 ms	16880 KB	Output is correct
5	Correct	355 ms	22012 KB	Output is correct
6	Correct	1487 ms	70644 KB	Output is correct
7	Correct	505 ms	25408 KB	Output is correct
8	Correct	595 ms	32696 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2688 KB	Output is correct
2	Correct	1547 ms	84708 KB	Output is correct
3	Execution timed out	3034 ms	286960 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2688 KB	Output is correct
2	Correct	3 ms	2688 KB	Output is correct
3	Correct	4 ms	2688 KB	Output is correct
4	Correct	5 ms	2560 KB	Output is correct
5	Correct	4 ms	2688 KB	Output is correct
6	Correct	4 ms	2688 KB	Output is correct
7	Correct	4 ms	2688 KB	Output is correct
8	Correct	5 ms	2688 KB	Output is correct
9	Correct	5 ms	2688 KB	Output is correct
10	Correct	4 ms	2688 KB	Output is correct
11	Correct	6 ms	2820 KB	Output is correct
12	Correct	5 ms	2816 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	5 ms	2816 KB	Output is correct
15	Correct	5 ms	2816 KB	Output is correct
16	Correct	4 ms	2816 KB	Output is correct
17	Correct	5 ms	2688 KB	Output is correct
18	Correct	6 ms	2688 KB	Output is correct
19	Correct	7 ms	3044 KB	Output is correct
20	Correct	8 ms	3072 KB	Output is correct
21	Correct	8 ms	2944 KB	Output is correct
22	Correct	34 ms	6928 KB	Output is correct
23	Correct	41 ms	6896 KB	Output is correct
24	Correct	50 ms	7048 KB	Output is correct
25	Correct	50 ms	7048 KB	Output is correct
26	Correct	55 ms	7176 KB	Output is correct
27	Correct	13 ms	3312 KB	Output is correct
28	Correct	10 ms	3328 KB	Output is correct
29	Correct	15 ms	3328 KB	Output is correct
30	Correct	117 ms	11196 KB	Output is correct
31	Correct	113 ms	11328 KB	Output is correct
32	Correct	99 ms	11432 KB	Output is correct
33	Correct	71 ms	8172 KB	Output is correct
34	Correct	80 ms	8304 KB	Output is correct
35	Correct	92 ms	7656 KB	Output is correct
36	Correct	1492 ms	86208 KB	Output is correct
37	Correct	1509 ms	85788 KB	Output is correct
38	Correct	1510 ms	85912 KB	Output is correct
39	Correct	569 ms	28108 KB	Output is correct
40	Correct	584 ms	28136 KB	Output is correct
41	Correct	616 ms	28276 KB	Output is correct
42	Correct	207 ms	16132 KB	Output is correct
43	Correct	1589 ms	141628 KB	Output is correct
44	Correct	1765 ms	141880 KB	Output is correct
45	Correct	1700 ms	141752 KB	Output is correct
46	Correct	1669 ms	141928 KB	Output is correct
47	Correct	1698 ms	141900 KB	Output is correct
48	Correct	1689 ms	141904 KB	Output is correct
49	Correct	1730 ms	141908 KB	Output is correct
50	Correct	1820 ms	141864 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2688 KB	Output is correct
2	Correct	3 ms	2688 KB	Output is correct
3	Correct	4 ms	2688 KB	Output is correct
4	Correct	5 ms	2560 KB	Output is correct
5	Correct	4 ms	2688 KB	Output is correct
6	Correct	4 ms	2688 KB	Output is correct
7	Correct	4 ms	2688 KB	Output is correct
8	Correct	5 ms	2688 KB	Output is correct
9	Correct	5 ms	2688 KB	Output is correct
10	Correct	4 ms	2688 KB	Output is correct
11	Correct	6 ms	2820 KB	Output is correct
12	Correct	5 ms	2816 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	5 ms	2816 KB	Output is correct
15	Correct	5 ms	2816 KB	Output is correct
16	Correct	4 ms	2816 KB	Output is correct
17	Correct	5 ms	2688 KB	Output is correct
18	Correct	6 ms	2688 KB	Output is correct
19	Correct	7 ms	3044 KB	Output is correct
20	Correct	8 ms	3072 KB	Output is correct
21	Correct	8 ms	2944 KB	Output is correct
22	Correct	34 ms	6928 KB	Output is correct
23	Correct	41 ms	6896 KB	Output is correct
24	Correct	50 ms	7048 KB	Output is correct
25	Correct	50 ms	7048 KB	Output is correct
26	Correct	55 ms	7176 KB	Output is correct
27	Correct	214 ms	16868 KB	Output is correct
28	Correct	215 ms	17892 KB	Output is correct
29	Correct	191 ms	18908 KB	Output is correct
30	Correct	206 ms	16880 KB	Output is correct
31	Correct	355 ms	22012 KB	Output is correct
32	Correct	1487 ms	70644 KB	Output is correct
33	Correct	505 ms	25408 KB	Output is correct
34	Correct	595 ms	32696 KB	Output is correct
35	Correct	4 ms	2688 KB	Output is correct
36	Correct	1547 ms	84708 KB	Output is correct
37	Execution timed out	3034 ms	286960 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #106520

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