oj.uz

Submission #106394

# Submission time Handle Problem Language Result Execution time Memory
106394 2019-04-18T09:30:20 Z username Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 313604 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;
 
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+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:48: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 5 ms 2688 KB Output is correct
4 Correct 4 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 4 ms 2688 KB Output is correct
8 Correct 5 ms 2688 KB Output is correct
9 Correct 5 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 6 ms 2816 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Correct 5 ms 2944 KB Output is correct
15 Correct 4 ms 2816 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 6 ms 2816 KB Output is correct
19 Correct 7 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 85 ms 10760 KB Output is correct
23 Correct 84 ms 10760 KB Output is correct
24 Correct 79 ms 10812 KB Output is correct
25 Correct 71 ms 10808 KB Output is correct
26 Correct 103 ms 10680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 26044 KB Output is correct
2 Correct 281 ms 25820 KB Output is correct
3 Correct 231 ms 25720 KB Output is correct
4 Correct 205 ms 25848 KB Output is correct
5 Correct 504 ms 26792 KB Output is correct
6 Correct 2496 ms 96540 KB Output is correct
7 Correct 645 ms 30376 KB Output is correct
8 Correct 1042 ms 39660 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 2620 ms 153380 KB Output is correct
3 Execution timed out 3044 ms 298272 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 3125 ms 313604 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 5 ms 2688 KB Output is correct
4 Correct 4 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 4 ms 2688 KB Output is correct
8 Correct 5 ms 2688 KB Output is correct
9 Correct 5 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 6 ms 2816 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Correct 5 ms 2944 KB Output is correct
15 Correct 4 ms 2816 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 6 ms 2816 KB Output is correct
19 Correct 7 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 85 ms 10760 KB Output is correct
23 Correct 84 ms 10760 KB Output is correct
24 Correct 79 ms 10812 KB Output is correct
25 Correct 71 ms 10808 KB Output is correct
26 Correct 103 ms 10680 KB Output is correct
27 Correct 18 ms 3456 KB Output is correct
28 Correct 10 ms 3456 KB Output is correct
29 Correct 11 ms 3456 KB Output is correct
30 Correct 203 ms 18972 KB Output is correct
31 Correct 183 ms 18872 KB Output is correct
32 Correct 191 ms 18844 KB Output is correct
33 Correct 95 ms 10360 KB Output is correct
34 Correct 91 ms 10352 KB Output is correct
35 Correct 117 ms 10388 KB Output is correct
36 Correct 2566 ms 157516 KB Output is correct
37 Correct 2521 ms 159556 KB Output is correct
38 Correct 2766 ms 159288 KB Output is correct
39 Correct 979 ms 29600 KB Output is correct
40 Correct 946 ms 29692 KB Output is correct
41 Correct 998 ms 29524 KB Output is correct
42 Correct 431 ms 17924 KB Output is correct
43 Execution timed out 3030 ms 275400 KB Time limit exceeded
44 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 5 ms 2688 KB Output is correct
4 Correct 4 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 4 ms 2688 KB Output is correct
8 Correct 5 ms 2688 KB Output is correct
9 Correct 5 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 6 ms 2816 KB Output is correct
13 Correct 5 ms 2816 KB Output is correct
14 Correct 5 ms 2944 KB Output is correct
15 Correct 4 ms 2816 KB Output is correct
16 Correct 5 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 6 ms 2816 KB Output is correct
19 Correct 7 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 85 ms 10760 KB Output is correct
23 Correct 84 ms 10760 KB Output is correct
24 Correct 79 ms 10812 KB Output is correct
25 Correct 71 ms 10808 KB Output is correct
26 Correct 103 ms 10680 KB Output is correct
27 Correct 337 ms 26044 KB Output is correct
28 Correct 281 ms 25820 KB Output is correct
29 Correct 231 ms 25720 KB Output is correct
30 Correct 205 ms 25848 KB Output is correct
31 Correct 504 ms 26792 KB Output is correct
32 Correct 2496 ms 96540 KB Output is correct
33 Correct 645 ms 30376 KB Output is correct
34 Correct 1042 ms 39660 KB Output is correct
35 Correct 5 ms 2688 KB Output is correct
36 Correct 2620 ms 153380 KB Output is correct
37 Execution timed out 3044 ms 298272 KB Time limit exceeded
38 Halted 0 ms 0 KB -