Submission #745091

#	Time	Username	Problem	Language	Result	Execution time	Memory
745091		b00norp	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3049 ms	1048576 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
const int INF = 1e18, N = 3e5 + 5;
vector<int> g[N];
bool vis[N];
 
bool cmp(array<int, 2> a, array<int, 2> b)
{
	if(a[0] != b[0])
	{
		return a[0] > b[0];
	}
	return a[1] < b[1];
}
 
void Solve() 
{
	int n;
	cin >> n;
	vector<array<int, 3> > circle(n + 1);
	for(int i = 1; i <= n; i++)
	{
		cin >> circle[i][0] >> circle[i][1] >> circle[i][2];
	}
	vector<array<int, 2> > order;
	for(int i = 1; i <= n; i++)
	{
		order.push_back({circle[i][2], i});
		for(int j = i + 1; j <= n; j++)
		{
			int x = abs(circle[i][0] - circle[j][0]), y = abs(circle[i][1] - circle[j][1]);
			int dist = x * x + y * y;
			if(dist <= (circle[i][2] + circle[j][2]) * (circle[i][2] + circle[j][2]))
			{
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}
	sort(order.begin(), order.end(), cmp);
	vector<int> res(n + 1, -1);
	for(int i = 0; i < order.size(); i++)
	{
		int idx = order[i][1];
		if(vis[idx]) continue;
		vis[idx] = true;
		res[idx] = idx;
		for(int j: g[idx])
		{
			if(!vis[j])
			{
				vis[j] = true;
				res[j] = idx;
			}
		}
	}
	// cout << "omk\n";
	for(int i = 1; i <= n; i++)
	{
		cout << res[i] << " ";
	}
	cout << "\n";
}
 
int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}
 
/*
Sample 1:
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: In function 'void Solve()':
circle_selection.cpp:46:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0; i < order.size(); i++)
      |                 ~~^~~~~~~~~~~~~~

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