oj.uz

Submission #106511

# Submission time Handle Problem Language Result Execution time Memory
106511 2019-04-19T02:17:57 Z username Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 287044 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,vector<pii>>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(pii(j,0));
				}
			}
		}
		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();++it){
				if(it->S)continue;
				C c=a[it->F];
				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->F]=1;
					it->S=1;
//					mp[x*bl+y].erase(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 5 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 5 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 5 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2560 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 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 2824 KB Output is correct
16 Correct 4 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 9 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 50 ms 7048 KB Output is correct
23 Correct 45 ms 6920 KB Output is correct
24 Correct 49 ms 6928 KB Output is correct
25 Correct 45 ms 7056 KB Output is correct
26 Correct 46 ms 7024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 20388 KB Output is correct
2 Correct 236 ms 23496 KB Output is correct
3 Correct 258 ms 23132 KB Output is correct
4 Correct 267 ms 22504 KB Output is correct
5 Correct 366 ms 27304 KB Output is correct
6 Correct 1451 ms 75244 KB Output is correct
7 Correct 412 ms 30728 KB Output is correct
8 Correct 578 ms 37760 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 1523 ms 84832 KB Output is correct
3 Execution timed out 3053 ms 287044 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 3101 ms 286060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 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 5 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2560 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 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 2824 KB Output is correct
16 Correct 4 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 9 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 50 ms 7048 KB Output is correct
23 Correct 45 ms 6920 KB Output is correct
24 Correct 49 ms 6928 KB Output is correct
25 Correct 45 ms 7056 KB Output is correct
26 Correct 46 ms 7024 KB Output is correct
27 Correct 11 ms 3456 KB Output is correct
28 Correct 10 ms 3728 KB Output is correct
29 Correct 10 ms 3664 KB Output is correct
30 Correct 103 ms 11628 KB Output is correct
31 Correct 99 ms 11576 KB Output is correct
32 Correct 106 ms 11636 KB Output is correct
33 Correct 84 ms 10540 KB Output is correct
34 Correct 98 ms 10872 KB Output is correct
35 Correct 88 ms 10072 KB Output is correct
36 Correct 1495 ms 87524 KB Output is correct
37 Correct 1541 ms 87476 KB Output is correct
38 Correct 1670 ms 87380 KB Output is correct
39 Correct 842 ms 29564 KB Output is correct
40 Correct 831 ms 29820 KB Output is correct
41 Correct 917 ms 29692 KB Output is correct
42 Correct 266 ms 17672 KB Output is correct
43 Correct 1729 ms 143464 KB Output is correct
44 Correct 1825 ms 143584 KB Output is correct
45 Correct 1789 ms 143580 KB Output is correct
46 Correct 1798 ms 143744 KB Output is correct
47 Correct 1726 ms 143772 KB Output is correct
48 Correct 1645 ms 143676 KB Output is correct
49 Correct 1850 ms 143812 KB Output is correct
50 Correct 1784 ms 143556 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 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 5 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2560 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 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 2824 KB Output is correct
16 Correct 4 ms 2816 KB Output is correct
17 Correct 4 ms 2816 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 9 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 50 ms 7048 KB Output is correct
23 Correct 45 ms 6920 KB Output is correct
24 Correct 49 ms 6928 KB Output is correct
25 Correct 45 ms 7056 KB Output is correct
26 Correct 46 ms 7024 KB Output is correct
27 Correct 210 ms 20388 KB Output is correct
28 Correct 236 ms 23496 KB Output is correct
29 Correct 258 ms 23132 KB Output is correct
30 Correct 267 ms 22504 KB Output is correct
31 Correct 366 ms 27304 KB Output is correct
32 Correct 1451 ms 75244 KB Output is correct
33 Correct 412 ms 30728 KB Output is correct
34 Correct 578 ms 37760 KB Output is correct
35 Correct 5 ms 2688 KB Output is correct
36 Correct 1523 ms 84832 KB Output is correct
37 Execution timed out 3053 ms 287044 KB Time limit exceeded
38 Halted 0 ms 0 KB -