답안 #106530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106530 2019-04-19T02:59:43 Z username 원 고르기 (APIO18_circle_selection) C++14
49 / 100
3000 ms 286228 KB
#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(){
      ^
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3027 ms 285008 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -