Submission #137504

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137504	2019-07-28T05:32:49 Z	임유진(#3281)	Countries (BOI06_countries)	C++14	100 / 100	3 ms	376 KB

countries

#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

#	Verdict	Execution time	Memory	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