oj.uz

Submission #980933

# Submission time Handle Problem Language Result Execution time Memory
980933 2024-05-12T15:57:34 Z AbdelmagedNour Circle selection (APIO18_circle_selection) C++17
0 / 100
 1085 ms 38852 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 38184 KB Output is correct
2 Correct 690 ms 38852 KB Output is correct
3 Incorrect 662 ms 20816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -