oj.uz

Submission #1104112

# Submission time Handle Problem Language Result Execution time Memory
1104112 2024-10-22T20:09:34 Z Kirill22 Countries (BOI06_countries) C++17
100 / 100
 4 ms 504 KB 
#include "bits/stdc++.h"
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    auto get = [&] (int i, int j) {
        return (a[i][0] - a[j][0]) * (a[i][0] - a[j][0]) + (a[i][1] - a[j][1]) * (a[i][1] - a[j][1]);
    };
    vector<int> ans(n);
    for (int j = 0; j < n; j++) {
        vector<array<int, 3>> st;
        for (int i = 0; i < n; i++) {
            if (i != j) {
                if (a[i][2] > a[j][2] * 1ll * get(i, j)) {
                    st.push_back({a[i][2], get(i, j), i});
                }
            }
        }
        vector<array<int, 3>> st2;
        for (auto [num, den, i] : st) {
            if (st2.empty() || st2[0][0] * 1ll * den < num * 1ll * st2[0][1]) {
                st2 = {{num, den, i}};
            } else if (st2[0][0] * 1ll * den == num * 1ll * st2[0][1]) {
                st2.push_back({num, den, i});
            }
        }
        if (st2.empty()) {
            ans[j] = -1;
        } else if ((int) st2.size() >= 2) {
            ans[j] = -2;
        } else {
            ans[j] = st2[0][2];
        }
    }
    for (int i = 0; i < n; i++) {
        while (ans[i] >= 0) {
            if (ans[ans[i]] < 0) {
                break;
            }
            ans[i] = ans[ans[i]];
        }
        if (ans[i] == -1) {
            cout << "K\n";
        } else if (ans[i] == -2) {
            cout << "D\n";
        } else {
            cout << ans[i] + 1 << '\n';
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 3 ms 336 KB Output is correct
19 Correct 4 ms 468 KB Output is correct
20 Correct 3 ms 336 KB Output is correct