oj.uz

Submission #511141

# Submission time Handle Problem Language Result Execution time Memory
511141 2022-01-15T08:54:59 Z inventiontime Countries (BOI06_countries) C++17
100 / 100
 4 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;

#define int ll
//#define endl '\n'

#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define re(x, n) x.clear(); x.resize(n)
#define all(x) (x).begin(), (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)
#define print(x) cout << #x << ": " << x << endl

//#define maxn ((int) 1e5 + 5)
#define inf ((int) 1e17)

typedef long long ll;
typedef priority_queue<int> pq;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a,b); return B; }

int n;
vti city;
vti top_threat;

int dist(int i, int j) {
    return abs(city[i][0] - city[j][0])*abs(city[i][0] - city[j][0]) + abs(city[i][1] - city[j][1])*abs(city[i][1] - city[j][1]);
}

bool threat(int i, int j) { // check if i is threatened by j
    return city[i][2] * dist(i, j) < city[j][2];
}

ti calc_threat(ti t1, ti t2) {
    if(t1[0] * t2[1] == t1[1] * t2[0]) {
        return {t1[0], t1[1], -2};
    } else if(t1[0] * t2[1] > t1[1] * t2[0]) { // influence of t1 is greater
        return t1;
    } else {
        return t2;
    }
}

void solve() {
    
    cin >> n;
    re(city, n);
    re(top_threat, n);

    loop(i, n) {
        int x, y, s;
        cin >> x >> y >> s;
        city[i] = {x, y, s};
        top_threat[i] = {-1, 1, -1};
    }

    loop(i, n) loop(j, n) if(i != j) {
        if(threat(i, j))
            top_threat[i] = calc_threat(top_threat[i], {city[j][2], dist(i, j), j});
    }

    loop(i, n) {
        int j = i;
        while(top_threat[j][2] >= 0) j = top_threat[j][2];
        if(j == i) cout << (top_threat[j][2] == -1 ? "K" : "D") << endl;
        else cout << j+1 << endl;
    }

}

signed main(){

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    //cout << flush;

    return 0;

}

Subtask #1
100.0 / 100.0

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