Submission #492557

#	Time	Username	Problem	Language	Result	Execution time	Memory
492557		vulpes	Countries (BOI06_countries)	C++17	10 / 100	5 ms	336 KiB

countries

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

const int N = 1007;

struct country {
    int x, y, s, ind;
} a[N];
bool operator <(country a, country b) {
    return (a.s != b.s ? a.s > b.s : a.ind < b.ind);
}
int dist(country x, country y) {
    return (x.x - y.x) * (x.x - y.x) +
           (x.y - y.y) * (x.y - y.y);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].s;
        a[i].ind = i;
    }
    sort(a, a + n);
    vector<string> ans(n);
    for (int i = 0; i < n; i++) {
        vector<country> v;
        for (int j = 0; j < i; j++) {
            if (a[j].s > dist(a[i], a[j]) * a[i].s) {
                v.push_back(a[j]);
            }
        }
        if (!v.size()) {
            ans[a[i].ind] = "K"; continue;
        }
        int i1 = 0, i2 = 0, d1, d2;
        for (int j = 0; j < v.size(); j++) {
            d1 = a[v[i1].ind].s * dist(a[i], v[j]);
            d2 = a[v[j].ind].s * dist(a[i], v[i1]);
            if (d1 > d2) {
                i2 = i1; i1 = j; continue;
            }
            d1 = a[v[i2].ind].s * dist(a[i], v[j]);
            d2 = a[v[j].ind].s * dist(a[i], v[i2]);
            if (d1 > d2) {
                i2 = j;
            }
        }
        if (i1 != i2) {
            ans[a[i].ind] = "D"; continue;
        }
        if (ans[v[i1].ind] != "K") {
            ans[a[i].ind] = ans[v[i1].ind]; continue;
        }
        ans[a[i].ind] = to_string(v[i1].ind + 1);
    }
    for (string i : ans) {
        cout << i << endl;
    }
}

Compilation message (stderr)

countries.cpp: In function 'int main()':
countries.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<country>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j = 0; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 10 / 100