oj.uz

Submission #835538

# Submission time Handle Problem Language Result Execution time Memory
835538 2023-08-23T15:34:12 Z jamielim Circle selection (APIO18_circle_selection) C++14
0 / 100
 2104 ms 39660 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    #define fi first
    #define se second
    #define mp make_pair
    #define pb emplace_back
    #define ALL(x) x.begin(),x.end()
    #define SZ(x) (int)x.size()
    typedef long long ll;
    typedef pair<int,int> ii;
    typedef pair<ii,ii> i4;
    typedef vector<int> vi;
    const int MOD=1000000007;
    const int INF=1012345678;
    const ll LLINF=1012345678012345678LL;
    const double PI=3.1415926536;
    const double EPS=1e-14;
     
    int n;
    i4 arr[300005];
    int ans[300005];
    set<i4> pq;
    int scale=(1<<30);
    map<int,vector<ii> > m;
     
    inline void downscale(){
    	scale/=2;
    	m.clear();
    	for(i4 i:pq){
    		m[i.se.fi/scale].pb(i.se.se/scale,-i.fi.se);
    	}
    	for(auto it=m.begin();it!=m.end();++it){
    		sort(ALL(it->se));
    	}
    }
     
    inline bool intersect(int a,int b){
    	ll dx=arr[a].se.fi-arr[b].se.fi;
    	ll dy=arr[a].se.se-arr[b].se.se;
    	ll r=arr[a].fi.fi+arr[b].fi.fi;
    	return (dx*dx<=r*r-dy*dy);
    }
     
    int main(){
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    		scanf("%d%d%d",&arr[i].se.fi,&arr[i].se.se,&arr[i].fi.fi);
    		arr[i].fi.se=-i;
    		pq.insert(arr[i]);
    	}
    	memset(ans,-1,sizeof(ans));
    	downscale();
    	while(!pq.empty()){
    		auto it=pq.end();--it;
    		i4 cur=(*it);pq.erase(it);
    		int index=-cur.fi.se;
    		if(ans[index]!=-1)continue;
    		ans[index]=index;
    		while(scale>cur.fi.fi){
    			downscale();
    		}
    		int x=cur.se.fi/scale,y=cur.se.se/scale;
    		for(int i=x-2;i<=x+2;i++){
    			int l=lower_bound(m[i].begin(),m[i].end(),mp(y-2,-INF))-m[i].begin();
    			int r=lower_bound(m[i].begin(),m[i].end(),mp(y+3,-INF))-m[i].begin()-1;
    			for(int j=l;j<=r;j++){
    				int idx=m[i][j].se;
    				if(ans[idx]==-1&&intersect(idx,index)){
    					i4 link=arr[idx];
    					pq.erase(link);
    					ans[idx]=index;
    				}
    			}
    		}
    	}
    	for(int i=0;i<n;i++)printf("%d ",ans[i]+1);
    }

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:46:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |      scanf("%d",&n);
      |      ~~~~~^~~~~~~~~
circle_selection.cpp:48:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |       scanf("%d%d%d",&arr[i].se.fi,&arr[i].se.se,&arr[i].fi.fi);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1456 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1456 KB Output is correct
15 Correct 1 ms 1456 KB Output is correct
16 Correct 2 ms 1492 KB Output is correct
17 Incorrect 2 ms 1492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 31016 KB Output is correct
2 Incorrect 532 ms 31188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Incorrect 565 ms 12140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2104 ms 39660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1456 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1456 KB Output is correct
15 Correct 1 ms 1456 KB Output is correct
16 Correct 2 ms 1492 KB Output is correct
17 Incorrect 2 ms 1492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1456 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1456 KB Output is correct
15 Correct 1 ms 1456 KB Output is correct
16 Correct 2 ms 1492 KB Output is correct
17 Incorrect 2 ms 1492 KB Output isn't correct
18 Halted 0 ms 0 KB -