oj.uz

Submission #106395

# Submission time Handle Problem Language Result Execution time Memory
106395 2019-04-18T09:45:01 Z username Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 287032 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***********************************/
#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,list<int>>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;});
	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){
			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:49: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 4 ms 2688 KB Output is correct
5 Correct 3 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 2688 KB Output is correct
10 Correct 4 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 5 ms 2816 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2788 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 11 ms 3072 KB Output is correct
20 Correct 10 ms 3072 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 49 ms 6920 KB Output is correct
23 Correct 47 ms 6960 KB Output is correct
24 Correct 35 ms 6920 KB Output is correct
25 Correct 37 ms 7048 KB Output is correct
26 Correct 40 ms 7060 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 25928 KB Output is correct
2 Correct 269 ms 25848 KB Output is correct
3 Correct 245 ms 25592 KB Output is correct
4 Correct 284 ms 25848 KB Output is correct
5 Correct 455 ms 26688 KB Output is correct
6 Correct 1446 ms 71032 KB Output is correct
7 Correct 569 ms 28024 KB Output is correct
8 Correct 691 ms 33256 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 1476 ms 84880 KB Output is correct
3 Execution timed out 3037 ms 287032 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 3068 ms 285860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.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 4 ms 2688 KB Output is correct
5 Correct 3 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 2688 KB Output is correct
10 Correct 4 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 5 ms 2816 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2788 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 11 ms 3072 KB Output is correct
20 Correct 10 ms 3072 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 49 ms 6920 KB Output is correct
23 Correct 47 ms 6960 KB Output is correct
24 Correct 35 ms 6920 KB Output is correct
25 Correct 37 ms 7048 KB Output is correct
26 Correct 40 ms 7060 KB Output is correct
27 Correct 11 ms 3456 KB Output is correct
28 Correct 13 ms 3584 KB Output is correct
29 Correct 11 ms 3456 KB Output is correct
30 Correct 114 ms 11196 KB Output is correct
31 Correct 101 ms 11192 KB Output is correct
32 Correct 96 ms 11324 KB Output is correct
33 Correct 101 ms 10436 KB Output is correct
34 Correct 87 ms 10360 KB Output is correct
35 Correct 121 ms 10404 KB Output is correct
36 Correct 1522 ms 86148 KB Output is correct
37 Correct 1489 ms 85764 KB Output is correct
38 Correct 1580 ms 85924 KB Output is correct
39 Correct 876 ms 28152 KB Output is correct
40 Correct 900 ms 28124 KB Output is correct
41 Correct 855 ms 28120 KB Output is correct
42 Correct 287 ms 16012 KB Output is correct
43 Correct 1720 ms 141644 KB Output is correct
44 Correct 1814 ms 144504 KB Output is correct
45 Correct 1767 ms 144324 KB Output is correct
46 Correct 1747 ms 144392 KB Output is correct
47 Correct 1726 ms 144612 KB Output is correct
48 Correct 1609 ms 144676 KB Output is correct
49 Correct 1748 ms 144432 KB Output is correct
50 Correct 1679 ms 144476 KB Output is correct

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 4 ms 2688 KB Output is correct
5 Correct 3 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 2688 KB Output is correct
10 Correct 4 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 5 ms 2816 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2788 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 11 ms 3072 KB Output is correct
20 Correct 10 ms 3072 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 49 ms 6920 KB Output is correct
23 Correct 47 ms 6960 KB Output is correct
24 Correct 35 ms 6920 KB Output is correct
25 Correct 37 ms 7048 KB Output is correct
26 Correct 40 ms 7060 KB Output is correct
27 Correct 248 ms 25928 KB Output is correct
28 Correct 269 ms 25848 KB Output is correct
29 Correct 245 ms 25592 KB Output is correct
30 Correct 284 ms 25848 KB Output is correct
31 Correct 455 ms 26688 KB Output is correct
32 Correct 1446 ms 71032 KB Output is correct
33 Correct 569 ms 28024 KB Output is correct
34 Correct 691 ms 33256 KB Output is correct
35 Correct 4 ms 2688 KB Output is correct
36 Correct 1476 ms 84880 KB Output is correct
37 Execution timed out 3037 ms 287032 KB Time limit exceeded
38 Halted 0 ms 0 KB -