oj.uz

Submission #492557

# Submission time Handle Problem Language Result Execution time Memory
492557 2021-12-08T00:21:41 Z vulpes Countries (BOI06_countries) C++17
10 / 100
 5 ms 336 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Incorrect 2 ms 336 KB Output isn't correct
7 Incorrect 2 ms 336 KB Output isn't correct
8 Incorrect 3 ms 336 KB Output isn't correct
9 Incorrect 2 ms 336 KB Output isn't correct
10 Incorrect 3 ms 336 KB Output isn't correct
11 Correct 1 ms 324 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 2 ms 336 KB Output isn't correct
15 Incorrect 1 ms 336 KB Output isn't correct
16 Incorrect 2 ms 336 KB Output isn't correct
17 Incorrect 2 ms 336 KB Output isn't correct
18 Incorrect 3 ms 336 KB Output isn't correct
19 Incorrect 5 ms 332 KB Output isn't correct
20 Incorrect 2 ms 336 KB Output isn't correct