oj.uz

Submission #835554

# Submission time Handle Problem Language Result Execution time Memory
835554 2023-08-23T15:47:07 Z jamielim Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 584268 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<ll,vector<int> > m;

inline void downscale(){
	m.clear();
	for(i4 i:pq){
		ll cur=(ll)(i.se.fi/scale)*(ll)(INF)+(ll)(i.se.se/scale);
		m[cur].pb(-i.fi.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].se.fi+=1000000000;arr[i].se.se+=1000000000;
		arr[i].fi.se=-i;
		pq.insert(arr[i]);
	}
	memset(ans,-1,sizeof(ans));
	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;
		bool change=0;
		while(scale>cur.fi.fi){
			scale/=2;
			change=1;
		}
		if(change)downscale();
		int x=cur.se.fi/scale,y=cur.se.se/scale;
		for(int i=x-2;i<=x+2;i++){
			for(int j=y-2;j<=y+2;j++){
				ll grid=(ll)(i)*(ll)(INF)+j;
				vector<int> v1=m[grid];
				vector<int> v2;
				for(int k:v1){
					if(intersect(k,index)){
						i4 link=arr[k];
						pq.erase(link);
						ans[k]=index;
					}else{
						v2.pb(k);
					}
				}
				swap(m[grid],v2);
			}
		}
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]+1);
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
circle_selection.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   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 1492 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1492 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 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 2 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1492 KB Output is correct
17 Incorrect 1 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 351 ms 27480 KB Output is correct
2 Incorrect 349 ms 27204 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 1492 KB Output is correct
2 Incorrect 1350 ms 92028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 584268 KB Time limit exceeded
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 1492 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1492 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 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 2 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1492 KB Output is correct
17 Incorrect 1 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 1492 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1492 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 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 2 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 1 ms 1492 KB Output is correct
17 Incorrect 1 ms 1492 KB Output isn't correct
18 Halted 0 ms 0 KB -