답안 #106511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106511	2019-04-19T02:17:57 Z	username	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3000 ms	287044 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<pii>>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(pii(j,0));
				}
			}
		}
		REP(x,a[i].x/k-2,a[i].x/k+3)REP(y,a[i].y/k-2,a[i].y/k+3){
			for(auto it=mp[x*bl+y].begin();it!=mp[x*bl+y].end();++it){
				if(it->S)continue;
				C c=a[it->F];
				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->F]=1;
					it->S=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	5 ms	2688 KB	Output is correct
2	Correct	4 ms	2688 KB	Output is correct
3	Correct	5 ms	2688 KB	Output is correct
4	Correct	5 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	5 ms	2688 KB	Output is correct
8	Correct	4 ms	2688 KB	Output is correct
9	Correct	4 ms	2560 KB	Output is correct
10	Correct	4 ms	2688 KB	Output is correct
11	Correct	5 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	5 ms	2816 KB	Output is correct
15	Correct	5 ms	2824 KB	Output is correct
16	Correct	4 ms	2816 KB	Output is correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2816 KB	Output is correct
19	Correct	9 ms	3072 KB	Output is correct
20	Correct	8 ms	3072 KB	Output is correct
21	Correct	8 ms	3072 KB	Output is correct
22	Correct	50 ms	7048 KB	Output is correct
23	Correct	45 ms	6920 KB	Output is correct
24	Correct	49 ms	6928 KB	Output is correct
25	Correct	45 ms	7056 KB	Output is correct
26	Correct	46 ms	7024 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	210 ms	20388 KB	Output is correct
2	Correct	236 ms	23496 KB	Output is correct
3	Correct	258 ms	23132 KB	Output is correct
4	Correct	267 ms	22504 KB	Output is correct
5	Correct	366 ms	27304 KB	Output is correct
6	Correct	1451 ms	75244 KB	Output is correct
7	Correct	412 ms	30728 KB	Output is correct
8	Correct	578 ms	37760 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2688 KB	Output is correct
2	Correct	1523 ms	84832 KB	Output is correct
3	Execution timed out	3053 ms	287044 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3101 ms	286060 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	4 ms	2688 KB	Output is correct
3	Correct	5 ms	2688 KB	Output is correct
4	Correct	5 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	5 ms	2688 KB	Output is correct
8	Correct	4 ms	2688 KB	Output is correct
9	Correct	4 ms	2560 KB	Output is correct
10	Correct	4 ms	2688 KB	Output is correct
11	Correct	5 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	5 ms	2816 KB	Output is correct
15	Correct	5 ms	2824 KB	Output is correct
16	Correct	4 ms	2816 KB	Output is correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2816 KB	Output is correct
19	Correct	9 ms	3072 KB	Output is correct
20	Correct	8 ms	3072 KB	Output is correct
21	Correct	8 ms	3072 KB	Output is correct
22	Correct	50 ms	7048 KB	Output is correct
23	Correct	45 ms	6920 KB	Output is correct
24	Correct	49 ms	6928 KB	Output is correct
25	Correct	45 ms	7056 KB	Output is correct
26	Correct	46 ms	7024 KB	Output is correct
27	Correct	11 ms	3456 KB	Output is correct
28	Correct	10 ms	3728 KB	Output is correct
29	Correct	10 ms	3664 KB	Output is correct
30	Correct	103 ms	11628 KB	Output is correct
31	Correct	99 ms	11576 KB	Output is correct
32	Correct	106 ms	11636 KB	Output is correct
33	Correct	84 ms	10540 KB	Output is correct
34	Correct	98 ms	10872 KB	Output is correct
35	Correct	88 ms	10072 KB	Output is correct
36	Correct	1495 ms	87524 KB	Output is correct
37	Correct	1541 ms	87476 KB	Output is correct
38	Correct	1670 ms	87380 KB	Output is correct
39	Correct	842 ms	29564 KB	Output is correct
40	Correct	831 ms	29820 KB	Output is correct
41	Correct	917 ms	29692 KB	Output is correct
42	Correct	266 ms	17672 KB	Output is correct
43	Correct	1729 ms	143464 KB	Output is correct
44	Correct	1825 ms	143584 KB	Output is correct
45	Correct	1789 ms	143580 KB	Output is correct
46	Correct	1798 ms	143744 KB	Output is correct
47	Correct	1726 ms	143772 KB	Output is correct
48	Correct	1645 ms	143676 KB	Output is correct
49	Correct	1850 ms	143812 KB	Output is correct
50	Correct	1784 ms	143556 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2688 KB	Output is correct
2	Correct	4 ms	2688 KB	Output is correct
3	Correct	5 ms	2688 KB	Output is correct
4	Correct	5 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	5 ms	2688 KB	Output is correct
8	Correct	4 ms	2688 KB	Output is correct
9	Correct	4 ms	2560 KB	Output is correct
10	Correct	4 ms	2688 KB	Output is correct
11	Correct	5 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	5 ms	2816 KB	Output is correct
15	Correct	5 ms	2824 KB	Output is correct
16	Correct	4 ms	2816 KB	Output is correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2816 KB	Output is correct
19	Correct	9 ms	3072 KB	Output is correct
20	Correct	8 ms	3072 KB	Output is correct
21	Correct	8 ms	3072 KB	Output is correct
22	Correct	50 ms	7048 KB	Output is correct
23	Correct	45 ms	6920 KB	Output is correct
24	Correct	49 ms	6928 KB	Output is correct
25	Correct	45 ms	7056 KB	Output is correct
26	Correct	46 ms	7024 KB	Output is correct
27	Correct	210 ms	20388 KB	Output is correct
28	Correct	236 ms	23496 KB	Output is correct
29	Correct	258 ms	23132 KB	Output is correct
30	Correct	267 ms	22504 KB	Output is correct
31	Correct	366 ms	27304 KB	Output is correct
32	Correct	1451 ms	75244 KB	Output is correct
33	Correct	412 ms	30728 KB	Output is correct
34	Correct	578 ms	37760 KB	Output is correct
35	Correct	5 ms	2688 KB	Output is correct
36	Correct	1523 ms	84832 KB	Output is correct
37	Execution timed out	3053 ms	287044 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #106511

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