oj.uz

Submission #106547

# Submission time Handle Problem Language Result Execution time Memory
106547 2019-04-19T03:31:23 Z username Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 284868 KB 
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define pb push_back
#define F first
#define S second
#define IOS cin.tie(0),ios_base::sync_with_stdio(false)
#define f2(x) ((x)*(x))

const int maxn=3e5+3,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,vector<int>>mp;
 
main(){
	IOS;
	cin>>n;
	int mnx=inf,mny=inf;
	REP(i,0,n)cin>>a[i].x>>a[i].y>>a[i].r,a[i].id=i,mnx=min(mnx,a[i].x),mny=min(mny,a[i].y);
	REP(i,0,n)a[i].x=a[i].x-mnx+1,a[i].y=a[i].y-mny+1;
	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]&&f2(a[i].x-a[*it].x)+f2(a[i].y-a[*it].y)<=f2(a[i].r+a[*it].r)){
					res[a[*it].id]=a[i].id;
					rmv[*it]=1;
				}
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

circle_selection.cpp:18: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 2 ms 384 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 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 3 ms 384 KB Output is correct
11 Correct 2 ms 384 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 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 37 ms 4624 KB Output is correct
23 Correct 24 ms 4624 KB Output is correct
24 Correct 51 ms 4624 KB Output is correct
25 Correct 36 ms 4680 KB Output is correct
26 Correct 37 ms 4624 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 15952 KB Output is correct
2 Correct 217 ms 14644 KB Output is correct
3 Correct 190 ms 16600 KB Output is correct
4 Correct 202 ms 15620 KB Output is correct
5 Correct 284 ms 19700 KB Output is correct
6 Correct 1344 ms 68364 KB Output is correct
7 Correct 367 ms 22908 KB Output is correct
8 Correct 554 ms 28724 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 1551 ms 82464 KB Output is correct
3 Execution timed out 3035 ms 284868 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 3046 ms 283760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
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 2 ms 384 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 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 3 ms 384 KB Output is correct
11 Correct 2 ms 384 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 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 37 ms 4624 KB Output is correct
23 Correct 24 ms 4624 KB Output is correct
24 Correct 51 ms 4624 KB Output is correct
25 Correct 36 ms 4680 KB Output is correct
26 Correct 37 ms 4624 KB Output is correct
27 Correct 9 ms 984 KB Output is correct
28 Correct 9 ms 1024 KB Output is correct
29 Correct 11 ms 944 KB Output is correct
30 Correct 91 ms 9020 KB Output is correct
31 Correct 109 ms 8892 KB Output is correct
32 Correct 99 ms 8980 KB Output is correct
33 Correct 79 ms 5744 KB Output is correct
34 Correct 93 ms 5932 KB Output is correct
35 Correct 70 ms 5360 KB Output is correct
36 Correct 1497 ms 83664 KB Output is correct
37 Correct 1489 ms 83688 KB Output is correct
38 Correct 1575 ms 83556 KB Output is correct
39 Correct 556 ms 25820 KB Output is correct
40 Correct 563 ms 25856 KB Output is correct
41 Correct 516 ms 25996 KB Output is correct
42 Correct 284 ms 13832 KB Output is correct
43 Correct 1661 ms 139464 KB Output is correct
44 Correct 1712 ms 139460 KB Output is correct
45 Correct 1716 ms 139316 KB Output is correct
46 Correct 1669 ms 139460 KB Output is correct
47 Correct 1727 ms 139588 KB Output is correct
48 Correct 1689 ms 139816 KB Output is correct
49 Execution timed out 3039 ms 139512 KB Time limit exceeded
50 Halted 0 ms 0 KB -

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 2 ms 384 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 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 3 ms 384 KB Output is correct
11 Correct 2 ms 384 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 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 37 ms 4624 KB Output is correct
23 Correct 24 ms 4624 KB Output is correct
24 Correct 51 ms 4624 KB Output is correct
25 Correct 36 ms 4680 KB Output is correct
26 Correct 37 ms 4624 KB Output is correct
27 Correct 187 ms 15952 KB Output is correct
28 Correct 217 ms 14644 KB Output is correct
29 Correct 190 ms 16600 KB Output is correct
30 Correct 202 ms 15620 KB Output is correct
31 Correct 284 ms 19700 KB Output is correct
32 Correct 1344 ms 68364 KB Output is correct
33 Correct 367 ms 22908 KB Output is correct
34 Correct 554 ms 28724 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 1551 ms 82464 KB Output is correct
37 Execution timed out 3035 ms 284868 KB Time limit exceeded
38 Halted 0 ms 0 KB -