oj.uz

답안 #137504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137504 2019-07-28T05:32:49 Z 임유진(#3281) Countries (BOI06_countries) C++14
100 / 100
 3 ms 376 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int X[MAXN], Y[MAXN], S[MAXN];
int ans[MAXN];			//-2 : kingdom, -1 : democracy
int ss[MAXN];

int dis(int a, int b) { return (X[a] - X[b]) * (X[a] - X[b]) + (Y[a] - Y[b]) * (Y[a] - Y[b]); }

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;

	cin >> N;
	for(int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> S[i];

	for(int i = 0; i < N; i++) ss[i] = i;
	sort(ss, ss + N, [&](const int a, const int b) { return S[a] < S[b]; } );

	for(int i = N - 1; i >= 0; i--) {
		int mx = N;
		bool two = false;
		for(int j = i + 1; j < N; j++) if(S[ss[j]] > S[ss[i]] * dis(ss[i], ss[j])) {
			if(S[ss[j]] * dis(mx, ss[i]) > S[mx] * dis(ss[j], ss[i])) {
				mx = ss[j];
				two = false;
			}
			else if(S[ss[j]] * dis(mx, ss[i]) == S[mx] * dis(ss[j], ss[i])) two = true;
		}
		if(mx == N) ans[ss[i]] = -2;
		else if(two) ans[ss[i]] = -1;
		else ans[ss[i]] = ans[mx] >= 0 ? ans[mx] : mx;
	}

	for(int i = 0; i < N; i++) {
		if(ans[i] >= 0) cout << ans[i] + 1 << "\n";
		else cout << (ans[i] == -2 ? "K\n" : "D\n");
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct