oj.uz

Submission #106391

# Submission time Handle Problem Language Result Execution time Memory
106391 2019-04-18T08:51:54 Z username Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 416580 KB 
#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***********************************/
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,set<int>>mp;

int f2(int x){
	return x*x;
}

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].insert(j);
				}
			}
		}
		REP(x,a[i].x/k-2,a[i].x/k+5)REP(y,a[i].y/k-2,a[i].y/k+5){
			for(auto it=mp[x*bl+y].begin();it!=mp[x*bl+y].end();){
				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++);
				}else ++it;
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory 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 5 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 5 ms 2944 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 5 ms 2944 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 5 ms 2816 KB Output is correct
19 Correct 8 ms 3328 KB Output is correct
20 Correct 9 ms 3380 KB Output is correct
21 Correct 9 ms 3328 KB Output is correct
22 Correct 100 ms 14776 KB Output is correct
23 Correct 107 ms 14748 KB Output is correct
24 Correct 95 ms 14780 KB Output is correct
25 Correct 88 ms 14908 KB Output is correct
26 Correct 105 ms 15164 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 31112 KB Output is correct
2 Correct 328 ms 31224 KB Output is correct
3 Correct 310 ms 30828 KB Output is correct
4 Correct 336 ms 31108 KB Output is correct
5 Correct 869 ms 32552 KB Output is correct
6 Correct 2968 ms 139492 KB Output is correct
7 Correct 978 ms 37560 KB Output is correct
8 Correct 1392 ms 51812 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 2937 ms 231056 KB Output is correct
3 Execution timed out 3047 ms 416580 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 406696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory 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 5 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 5 ms 2944 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 5 ms 2944 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 5 ms 2816 KB Output is correct
19 Correct 8 ms 3328 KB Output is correct
20 Correct 9 ms 3380 KB Output is correct
21 Correct 9 ms 3328 KB Output is correct
22 Correct 100 ms 14776 KB Output is correct
23 Correct 107 ms 14748 KB Output is correct
24 Correct 95 ms 14780 KB Output is correct
25 Correct 88 ms 14908 KB Output is correct
26 Correct 105 ms 15164 KB Output is correct
27 Correct 9 ms 3468 KB Output is correct
28 Correct 13 ms 3584 KB Output is correct
29 Correct 13 ms 3712 KB Output is correct
30 Correct 236 ms 26760 KB Output is correct
31 Correct 253 ms 26640 KB Output is correct
32 Correct 251 ms 26688 KB Output is correct
33 Correct 98 ms 11936 KB Output is correct
34 Correct 118 ms 11896 KB Output is correct
35 Correct 124 ms 12024 KB Output is correct
36 Execution timed out 3104 ms 237612 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory 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 5 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 5 ms 2944 KB Output is correct
13 Correct 5 ms 2944 KB Output is correct
14 Correct 5 ms 2944 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 5 ms 2816 KB Output is correct
19 Correct 8 ms 3328 KB Output is correct
20 Correct 9 ms 3380 KB Output is correct
21 Correct 9 ms 3328 KB Output is correct
22 Correct 100 ms 14776 KB Output is correct
23 Correct 107 ms 14748 KB Output is correct
24 Correct 95 ms 14780 KB Output is correct
25 Correct 88 ms 14908 KB Output is correct
26 Correct 105 ms 15164 KB Output is correct
27 Correct 319 ms 31112 KB Output is correct
28 Correct 328 ms 31224 KB Output is correct
29 Correct 310 ms 30828 KB Output is correct
30 Correct 336 ms 31108 KB Output is correct
31 Correct 869 ms 32552 KB Output is correct
32 Correct 2968 ms 139492 KB Output is correct
33 Correct 978 ms 37560 KB Output is correct
34 Correct 1392 ms 51812 KB Output is correct
35 Correct 4 ms 2688 KB Output is correct
36 Correct 2937 ms 231056 KB Output is correct
37 Execution timed out 3047 ms 416580 KB Time limit exceeded
38 Halted 0 ms 0 KB -