답안 #106518

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

circle_selection

#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid (l+r>>1)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#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);
				}
			}
		}
		REP(x,a[i].x/k-2,a[i].x/k+3)REP(y,a[i].y/k-2,a[i].y/k+3){
			auto&mmp=mp[x*bl+y];
//			auto end=mp[x*bl+y].end();
			for(auto it=mmp.begin();it!=mmp.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:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2688 KB	Output is correct
2	Correct	4 ms	2688 KB	Output is correct
3	Correct	4 ms	2688 KB	Output is correct
4	Correct	3 ms	2688 KB	Output is correct
5	Correct	4 ms	2688 KB	Output is correct
6	Correct	4 ms	2688 KB	Output is correct
7	Correct	3 ms	2688 KB	Output is correct
8	Correct	4 ms	2688 KB	Output is correct
9	Correct	3 ms	2688 KB	Output is correct
10	Correct	3 ms	2688 KB	Output is correct
11	Correct	4 ms	2816 KB	Output is correct
12	Correct	4 ms	2816 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	4 ms	2816 KB	Output is correct
15	Correct	4 ms	2816 KB	Output is correct
16	Correct	5 ms	2688 KB	Output is correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2816 KB	Output is correct
19	Correct	6 ms	3072 KB	Output is correct
20	Correct	7 ms	3072 KB	Output is correct
21	Correct	7 ms	2944 KB	Output is correct
22	Correct	28 ms	7036 KB	Output is correct
23	Correct	115 ms	6908 KB	Output is correct
24	Correct	38 ms	6920 KB	Output is correct
25	Correct	38 ms	6968 KB	Output is correct
26	Correct	33 ms	7008 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	170 ms	17000 KB	Output is correct
2	Correct	224 ms	18020 KB	Output is correct
3	Correct	204 ms	18784 KB	Output is correct
4	Correct	258 ms	16884 KB	Output is correct
5	Correct	280 ms	21888 KB	Output is correct
6	Correct	1331 ms	70636 KB	Output is correct
7	Correct	406 ms	25216 KB	Output is correct
8	Correct	498 ms	32600 KB	Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2688 KB	Output is correct
2	Correct	4 ms	2688 KB	Output is correct
3	Correct	4 ms	2688 KB	Output is correct
4	Correct	3 ms	2688 KB	Output is correct
5	Correct	4 ms	2688 KB	Output is correct
6	Correct	4 ms	2688 KB	Output is correct
7	Correct	3 ms	2688 KB	Output is correct
8	Correct	4 ms	2688 KB	Output is correct
9	Correct	3 ms	2688 KB	Output is correct
10	Correct	3 ms	2688 KB	Output is correct
11	Correct	4 ms	2816 KB	Output is correct
12	Correct	4 ms	2816 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	4 ms	2816 KB	Output is correct
15	Correct	4 ms	2816 KB	Output is correct
16	Correct	5 ms	2688 KB	Output is correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2816 KB	Output is correct
19	Correct	6 ms	3072 KB	Output is correct
20	Correct	7 ms	3072 KB	Output is correct
21	Correct	7 ms	2944 KB	Output is correct
22	Correct	28 ms	7036 KB	Output is correct
23	Correct	115 ms	6908 KB	Output is correct
24	Correct	38 ms	6920 KB	Output is correct
25	Correct	38 ms	6968 KB	Output is correct
26	Correct	33 ms	7008 KB	Output is correct
27	Correct	9 ms	3312 KB	Output is correct
28	Correct	12 ms	3328 KB	Output is correct
29	Correct	10 ms	3328 KB	Output is correct
30	Correct	107 ms	11332 KB	Output is correct
31	Correct	105 ms	11320 KB	Output is correct
32	Correct	100 ms	11344 KB	Output is correct
33	Correct	83 ms	8172 KB	Output is correct
34	Correct	75 ms	8328 KB	Output is correct
35	Correct	79 ms	7640 KB	Output is correct
36	Correct	1600 ms	86024 KB	Output is correct
37	Correct	1614 ms	85700 KB	Output is correct
38	Correct	1646 ms	85624 KB	Output is correct
39	Correct	659 ms	28252 KB	Output is correct
40	Correct	668 ms	28260 KB	Output is correct
41	Correct	729 ms	28260 KB	Output is correct
42	Correct	244 ms	15980 KB	Output is correct
43	Correct	1836 ms	141632 KB	Output is correct
44	Correct	1710 ms	141796 KB	Output is correct
45	Correct	1740 ms	141980 KB	Output is correct
46	Correct	1754 ms	141844 KB	Output is correct
47	Correct	1734 ms	141848 KB	Output is correct
48	Correct	1702 ms	141912 KB	Output is correct
49	Correct	1911 ms	142024 KB	Output is correct
50	Correct	1818 ms	141804 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2688 KB	Output is correct
2	Correct	4 ms	2688 KB	Output is correct
3	Correct	4 ms	2688 KB	Output is correct
4	Correct	3 ms	2688 KB	Output is correct
5	Correct	4 ms	2688 KB	Output is correct
6	Correct	4 ms	2688 KB	Output is correct
7	Correct	3 ms	2688 KB	Output is correct
8	Correct	4 ms	2688 KB	Output is correct
9	Correct	3 ms	2688 KB	Output is correct
10	Correct	3 ms	2688 KB	Output is correct
11	Correct	4 ms	2816 KB	Output is correct
12	Correct	4 ms	2816 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	4 ms	2816 KB	Output is correct
15	Correct	4 ms	2816 KB	Output is correct
16	Correct	5 ms	2688 KB	Output is correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2816 KB	Output is correct
19	Correct	6 ms	3072 KB	Output is correct
20	Correct	7 ms	3072 KB	Output is correct
21	Correct	7 ms	2944 KB	Output is correct
22	Correct	28 ms	7036 KB	Output is correct
23	Correct	115 ms	6908 KB	Output is correct
24	Correct	38 ms	6920 KB	Output is correct
25	Correct	38 ms	6968 KB	Output is correct
26	Correct	33 ms	7008 KB	Output is correct
27	Correct	170 ms	17000 KB	Output is correct
28	Correct	224 ms	18020 KB	Output is correct
29	Correct	204 ms	18784 KB	Output is correct
30	Correct	258 ms	16884 KB	Output is correct
31	Correct	280 ms	21888 KB	Output is correct
32	Correct	1331 ms	70636 KB	Output is correct
33	Correct	406 ms	25216 KB	Output is correct
34	Correct	498 ms	32600 KB	Output is correct
35	Correct	4 ms	2688 KB	Output is correct
36	Correct	1421 ms	84756 KB	Output is correct
37	Execution timed out	3056 ms	287036 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #106518

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