제출 #1070857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1070857		pawned	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	3072 ms	13952 KiB

circle_selection

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

bool intersect(pair<ii, int> c1, pair<ii, int> c2) {
	ll dx = abs(c1.fi.fi - c2.fi.fi);
	ll dy = abs(c1.fi.se - c2.fi.se);
	ll dt = c1.se + c2.se;
	if (dt * dt >= dx * dx + dy * dy)
		return true;
	return false;
}

int main() {
	fastIO();
	int N;
	cin>>N;
	vector<pair<ii, int>> cr(N);
	// {{x, y}, r}
	for (int i = 0; i < N; i++) {
		cin>>cr[i].fi.fi>>cr[i].fi.se>>cr[i].se;
	}
	vector<bool> used(N, false);
	vi par(N, -1);
	int rem = N;
	while (rem != 0) {
		int pos = -1;	// circle to use
		for (int i = 0; i < N; i++) {
			if (used[i])
				continue;
			if (pos == -1 || cr[i].se > cr[pos].se)
				pos = i;
		}
//		cout<<"pos: "<<pos<<endl;
//		cout<<"rem: "<<rem<<endl;
		for (int i = 0; i < N; i++) {
			if (used[i])
				continue;
			if (intersect(cr[pos], cr[i])) {
				// if i = pos, the circle intersects itself
				par[i] = pos;
				used[i] = true;
				rem--;
			}
		}
	}
//	cout<<"ANSWER: ";
	for (int x : par)
		cout<<(x + 1)<<" ";
	cout<<endl;
}

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