Submission #1104112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104112		Kirill22	Countries (BOI06_countries)	C++17	100 / 100	4 ms	504 KiB

countries

#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 / 100