Submission #980933

#	Time	Username	Problem	Language	Result	Execution time	Memory
980933		AbdelmagedNour	Circle selection (APIO18_circle_selection)	C++17	0 / 100	1085 ms	38852 KiB

circle_selection

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=300005;
bool check(array<ll,3>&a,array<ll,3>&b){
	ll x=a[0]-b[0],y=a[1]-b[1],len=a[2]+b[2];
	return x*x<=len*len-y*y;
}
int ans[N];
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<array<ll,3>>circle(n);
	for(int i=0;i<n;i++){
		cin>>circle[i][0]>>circle[i][1]>>circle[i][2];
		circle[i][0]+=(1<<30);
		circle[i][1]+=(1<<30);
	}
	vector<int>order(n);
	iota(order.begin(),order.end(),0);
	sort(order.begin(),order.end(),[&](int i,int j){
		if(circle[i][2]==circle[j][2])return i<j;
		return circle[i][2]>circle[j][2];
	});
	ll D=1e18;
	vector<int>sp;
	map<pair<ll,ll>,int>blk;
	for(auto i:order){
		if(circle[i][2]<D){
			D=circle[i][2];
			blk.clear();
			for(auto j:sp){
				ll x=circle[j][0]/D,y=circle[j][1]/D;
				assert(!blk.count({x,y}));
				blk[{x,y}]=j;
			}
		}
		ll x=circle[i][0]/D,y=circle[i][1]/D;
		ans[i]=i;
		for(int dx=-3;dx<=3&&(ans[i]==i);dx++){
			for(int dy=-3;dy<=3&&(ans[i]==i);dy++){
				if(blk.count({x+dx,y+dy})){
					int j=blk[{x+dx,y+dy}];
					if(check(circle[i],circle[j])){
						ans[i]=j;
						break;
					}
				}
			}
		}
		if(ans[i]==i){
			assert(!blk.count({x,y}));
			blk[{x,y}]=i;sp.push_back(i);
		}
	}
	for(int i=0;i<n;i++)cout<<ans[i]+1<<" ";
	
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13