Submission #106517

#	Time	Username	Problem	Language	Result	Execution time	Memory
106517		bert30702	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3017 ms	21244 KiB

circle_selection

#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef complex<long double> C;
const int MX = 3e5 + 100;
const double EPS = 1e-5;
struct circle { C p; int r, i; } v[MX];
int ans[MX];
bool touch(int a, int b) {
	return !ans[v[b].i] and abs(v[b].p - v[a].p) - EPS <= v[a].r + v[b].r;
}
main () {
	srand(time(0));
	int n; cin >> n;
	for(int i = 1; i <= n; i ++) {
		int x, y, r; cin >> x >> y >> r;
		v[i] = {{x, y}, r, i};
	}
	int ang = rand();
	for(int i = 1; i <= n; i ++) v[i].p *= C{cos(ang), sin(ang)};
	sort(v + 1, v + 1 + n, [](circle a, circle b) { return a.p.X < b.p.X; });
	priority_queue<pair<int, pii> > pq;
	for(int i = 1; i <= n; i ++) pq.push({v[i].r, {-v[i].i, -i}});
	while(pq.size()) {
		int p = -pq.top().S.S; pq.pop();
		if(ans[v[p].i]) continue;
		int cnta = 0, cntb = 0;
		for(int i = p; i >= 1 and cnta < 1000; i --) {
			if(ans[v[i].i]) continue;
			if(touch(p, i)) ans[v[i].i] = v[p].i;
			else cnta ++;
		}
		for(int i = p + 1; i <= n and cntb < 1000; i ++) {
			if(ans[v[i].i]) continue;
			if(touch(p, i)) ans[v[i].i] = v[p].i;
			else cntb ++;
		} 
	}
	for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Compilation message (stderr)

circle_selection.cpp:16:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:21:23: warning: narrowing conversion of 'x' from 'int' to 'long double' inside { } [-Wnarrowing]
   v[i] = {{x, y}, r, i};
                       ^
circle_selection.cpp:21:23: warning: narrowing conversion of 'y' from 'int' to 'long double' inside { } [-Wnarrowing]

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