Submission #1086457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086457		toast12	Countries (BOI06_countries)	C++14	100 / 100	190 ms	480 KiB

countries

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

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    vector<pair<int, int>> cities(n);
    for (int i = 0; i < n; i++) {
        cin >> cities[i].first >> cities[i].second >> s[i];
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        map<double, pair<int, int>> cnt;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            int x1 = cities[i].first, x2 = cities[j].first;
            int y1 = cities[i].second, y2 = cities[j].second;
            double dist = abs(x1-x2)*abs(x1-x2) + abs(y1-y2)*abs(y1-y2);
            cnt[s[j]/dist].first++;
            cnt[s[j]/dist].second = j;
        }
        auto it = cnt.rbegin();
        if (it->first > s[i]) {
            if (it->second.first > 1) ans[i] = -2;
            else ans[i] = it->second.second;
        }
        else ans[i] = -1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[j] = (ans[j] < 0 || ans[ans[j]] < 0 ? ans[j] : ans[ans[j]]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (ans[i] == -1) cout << "K\n";
        else if (ans[i] == -2) cout << "D\n";
        else cout << ans[i]+1 << '\n';
    }
    return 0;
}

• Subtask 1: 100 / 100