oj.uz

Submission #106533

# Submission time Handle Problem Language Result Execution time Memory
106533 2019-04-19T03:05:32 Z username Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 284804 KB 
#pragma GCC optimize("O3")
#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 pb emplace_back
#define F first
#define S second
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define f2(x) ((x)*(x))

const int maxn=3e5+9,inf=1ll<<60,bl=2e9+3;
struct C{int x,y,r,id;}a[maxn];
int n,res[maxn];
bitset<maxn>rmv;
unordered_map<int,VI>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,i,n){
				if(!rmv[j]){
					mp[a[j].x/k*bl+a[j].y/k].pb(j);
				}
			}
		}
		int xx=a[i].x/k,yy=a[i].y/k;
		REP(x,xx-2,xx+3)REP(y,yy-2,yy+3){
			auto&tls=mp[x*bl+y];
			for(auto it=tls.begin();it!=tls.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;
				}
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

circle_selection.cpp:20: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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 7 ms 768 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 39 ms 4624 KB Output is correct
23 Correct 31 ms 4624 KB Output is correct
24 Correct 34 ms 4624 KB Output is correct
25 Correct 28 ms 4624 KB Output is correct
26 Correct 33 ms 4744 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 14804 KB Output is correct
2 Correct 218 ms 16108 KB Output is correct
3 Correct 221 ms 16608 KB Output is correct
4 Correct 207 ms 14848 KB Output is correct
5 Correct 329 ms 19496 KB Output is correct
6 Correct 1356 ms 68288 KB Output is correct
7 Correct 305 ms 22920 KB Output is correct
8 Correct 524 ms 28324 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1448 ms 82420 KB Output is correct
3 Execution timed out 3052 ms 284804 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 3038 ms 283676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 7 ms 768 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 39 ms 4624 KB Output is correct
23 Correct 31 ms 4624 KB Output is correct
24 Correct 34 ms 4624 KB Output is correct
25 Correct 28 ms 4624 KB Output is correct
26 Correct 33 ms 4744 KB Output is correct
27 Correct 8 ms 1008 KB Output is correct
28 Correct 9 ms 1024 KB Output is correct
29 Correct 12 ms 896 KB Output is correct
30 Correct 92 ms 8920 KB Output is correct
31 Correct 74 ms 8988 KB Output is correct
32 Correct 97 ms 8992 KB Output is correct
33 Correct 84 ms 5868 KB Output is correct
34 Correct 70 ms 6004 KB Output is correct
35 Correct 78 ms 5224 KB Output is correct
36 Correct 1397 ms 83724 KB Output is correct
37 Correct 1449 ms 83536 KB Output is correct
38 Correct 1485 ms 83368 KB Output is correct
39 Correct 533 ms 25772 KB Output is correct
40 Correct 514 ms 25820 KB Output is correct
41 Correct 517 ms 25968 KB Output is correct
42 Correct 297 ms 13732 KB Output is correct
43 Correct 1709 ms 139488 KB Output is correct
44 Correct 1864 ms 139536 KB Output is correct
45 Correct 1905 ms 139256 KB Output is correct
46 Correct 1627 ms 139452 KB Output is correct
47 Correct 1799 ms 139472 KB Output is correct
48 Correct 1740 ms 139472 KB Output is correct
49 Correct 2499 ms 139648 KB Output is correct
50 Correct 1925 ms 139396 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 7 ms 768 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 39 ms 4624 KB Output is correct
23 Correct 31 ms 4624 KB Output is correct
24 Correct 34 ms 4624 KB Output is correct
25 Correct 28 ms 4624 KB Output is correct
26 Correct 33 ms 4744 KB Output is correct
27 Correct 193 ms 14804 KB Output is correct
28 Correct 218 ms 16108 KB Output is correct
29 Correct 221 ms 16608 KB Output is correct
30 Correct 207 ms 14848 KB Output is correct
31 Correct 329 ms 19496 KB Output is correct
32 Correct 1356 ms 68288 KB Output is correct
33 Correct 305 ms 22920 KB Output is correct
34 Correct 524 ms 28324 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 1448 ms 82420 KB Output is correct
37 Execution timed out 3052 ms 284804 KB Time limit exceeded
38 Halted 0 ms 0 KB -