oj.uz

Submission #106546

# Submission time Handle Problem Language Result Execution time Memory
106546 2019-04-19T03:29:19 Z username Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 284624 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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 2 ms 384 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 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 2 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 5 ms 768 KB Output is correct
20 Correct 5 ms 768 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 43 ms 4612 KB Output is correct
23 Correct 35 ms 4616 KB Output is correct
24 Correct 49 ms 4764 KB Output is correct
25 Correct 37 ms 4744 KB Output is correct
26 Correct 33 ms 4624 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 15840 KB Output is correct
2 Correct 182 ms 14644 KB Output is correct
3 Correct 205 ms 16600 KB Output is correct
4 Correct 178 ms 15468 KB Output is correct
5 Correct 297 ms 19624 KB Output is correct
6 Correct 1311 ms 68460 KB Output is correct
7 Correct 357 ms 22984 KB Output is correct
8 Correct 623 ms 28776 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 1345 ms 82356 KB Output is correct
3 Execution timed out 3038 ms 284624 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 3024 ms 283720 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 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 2 ms 384 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 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 2 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 5 ms 768 KB Output is correct
20 Correct 5 ms 768 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 43 ms 4612 KB Output is correct
23 Correct 35 ms 4616 KB Output is correct
24 Correct 49 ms 4764 KB Output is correct
25 Correct 37 ms 4744 KB Output is correct
26 Correct 33 ms 4624 KB Output is correct
27 Correct 7 ms 984 KB Output is correct
28 Correct 7 ms 1024 KB Output is correct
29 Correct 8 ms 1024 KB Output is correct
30 Correct 86 ms 9020 KB Output is correct
31 Correct 100 ms 9020 KB Output is correct
32 Correct 89 ms 9016 KB Output is correct
33 Correct 69 ms 5872 KB Output is correct
34 Correct 77 ms 5768 KB Output is correct
35 Correct 66 ms 5360 KB Output is correct
36 Correct 1469 ms 83764 KB Output is correct
37 Correct 1353 ms 83408 KB Output is correct
38 Correct 1430 ms 83360 KB Output is correct
39 Correct 514 ms 25912 KB Output is correct
40 Correct 464 ms 25872 KB Output is correct
41 Correct 527 ms 25876 KB Output is correct
42 Correct 292 ms 13916 KB Output is correct
43 Correct 1672 ms 139620 KB Output is correct
44 Correct 1713 ms 139484 KB Output is correct
45 Correct 1739 ms 139492 KB Output is correct
46 Correct 1647 ms 139576 KB Output is correct
47 Correct 1635 ms 139636 KB Output is correct
48 Correct 1793 ms 139716 KB Output is correct
49 Correct 2820 ms 139716 KB Output is correct
50 Correct 1747 ms 139584 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 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 2 ms 384 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 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 2 ms 512 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 5 ms 768 KB Output is correct
20 Correct 5 ms 768 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 43 ms 4612 KB Output is correct
23 Correct 35 ms 4616 KB Output is correct
24 Correct 49 ms 4764 KB Output is correct
25 Correct 37 ms 4744 KB Output is correct
26 Correct 33 ms 4624 KB Output is correct
27 Correct 282 ms 15840 KB Output is correct
28 Correct 182 ms 14644 KB Output is correct
29 Correct 205 ms 16600 KB Output is correct
30 Correct 178 ms 15468 KB Output is correct
31 Correct 297 ms 19624 KB Output is correct
32 Correct 1311 ms 68460 KB Output is correct
33 Correct 357 ms 22984 KB Output is correct
34 Correct 623 ms 28776 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 1345 ms 82356 KB Output is correct
37 Execution timed out 3038 ms 284624 KB Time limit exceeded
38 Halted 0 ms 0 KB -