답안 #106523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106523	2019-04-19T02:46:19 Z	username	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3000 ms	286284 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;});
	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 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: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	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	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 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	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	7 ms	768 KB	Output is correct
20	Correct	6 ms	768 KB	Output is correct
21	Correct	7 ms	640 KB	Output is correct
22	Correct	44 ms	4716 KB	Output is correct
23	Correct	40 ms	4616 KB	Output is correct
24	Correct	29 ms	4752 KB	Output is correct
25	Correct	30 ms	4752 KB	Output is correct
26	Correct	29 ms	4744 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	16864 KB	Output is correct
2	Correct	278 ms	18016 KB	Output is correct
3	Correct	194 ms	18860 KB	Output is correct
4	Correct	174 ms	16876 KB	Output is correct
5	Correct	298 ms	21924 KB	Output is correct
6	Correct	1398 ms	70508 KB	Output is correct
7	Correct	370 ms	25224 KB	Output is correct
8	Correct	466 ms	32696 KB	Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3043 ms	284752 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	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 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	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	7 ms	768 KB	Output is correct
20	Correct	6 ms	768 KB	Output is correct
21	Correct	7 ms	640 KB	Output is correct
22	Correct	44 ms	4716 KB	Output is correct
23	Correct	40 ms	4616 KB	Output is correct
24	Correct	29 ms	4752 KB	Output is correct
25	Correct	30 ms	4752 KB	Output is correct
26	Correct	29 ms	4744 KB	Output is correct
27	Correct	10 ms	1024 KB	Output is correct
28	Correct	8 ms	1024 KB	Output is correct
29	Correct	9 ms	1024 KB	Output is correct
30	Correct	90 ms	9016 KB	Output is correct
31	Correct	94 ms	9024 KB	Output is correct
32	Correct	98 ms	9028 KB	Output is correct
33	Correct	63 ms	6608 KB	Output is correct
34	Correct	71 ms	6724 KB	Output is correct
35	Correct	84 ms	6120 KB	Output is correct
36	Correct	1513 ms	84600 KB	Output is correct
37	Correct	1482 ms	84168 KB	Output is correct
38	Correct	1491 ms	84240 KB	Output is correct
39	Correct	589 ms	26768 KB	Output is correct
40	Correct	588 ms	26716 KB	Output is correct
41	Correct	607 ms	26700 KB	Output is correct
42	Correct	232 ms	14600 KB	Output is correct
43	Correct	1708 ms	140100 KB	Output is correct
44	Correct	1677 ms	140356 KB	Output is correct
45	Correct	1680 ms	140112 KB	Output is correct
46	Correct	1714 ms	140432 KB	Output is correct
47	Correct	1632 ms	140616 KB	Output is correct
48	Correct	1645 ms	140612 KB	Output is correct
49	Correct	1895 ms	140568 KB	Output is correct
50	Correct	1834 ms	140360 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	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	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 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	2 ms	512 KB	Output is correct
15	Correct	2 ms	512 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	7 ms	768 KB	Output is correct
20	Correct	6 ms	768 KB	Output is correct
21	Correct	7 ms	640 KB	Output is correct
22	Correct	44 ms	4716 KB	Output is correct
23	Correct	40 ms	4616 KB	Output is correct
24	Correct	29 ms	4752 KB	Output is correct
25	Correct	30 ms	4752 KB	Output is correct
26	Correct	29 ms	4744 KB	Output is correct
27	Correct	212 ms	16864 KB	Output is correct
28	Correct	278 ms	18016 KB	Output is correct
29	Correct	194 ms	18860 KB	Output is correct
30	Correct	174 ms	16876 KB	Output is correct
31	Correct	298 ms	21924 KB	Output is correct
32	Correct	1398 ms	70508 KB	Output is correct
33	Correct	370 ms	25224 KB	Output is correct
34	Correct	466 ms	32696 KB	Output is correct
35	Correct	2 ms	384 KB	Output is correct
36	Correct	1556 ms	83368 KB	Output is correct
37	Execution timed out	3099 ms	286284 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

답안 #106523

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