Submission #525156

#	Time	Username	Problem	Language	Result	Execution time	Memory
525156		ali22413836	Countries (BOI06_countries)	C++14	100 / 100	6 ms	6816 KiB

countries

#include <bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
    if(y == 0) return 1 ;
    if(y == 1) return x ;
    ll ret = mypower(x , y / 2);
    ret = (ret * ret) % mod;
    if(y % 2) ret = ( ret * x ) % mod ;
    return ret ;
}
struct ali{
    ll x , y , s , ind ;
    bool operator <(ali q){
        return s > q.s ;
    }
}a[200009] ;
vector < ll > v[200009];
ll n , ans[200009] ;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n ;
    for(int i = 0 ; i < n ; i++){
        ll f , s , t ;
        cin >> f >> s >> t ;
        a[i] = {f , s , t , i} ;
    }
    sort(a , a + n) ;
    for(int i = 0 ; i < n ; i++){
//        cout << a[i].ind << endl  ;
        for(int j = 0 ; j < n ; j++){
            if(j == i)
                continue ;
            ll dis1 = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y) ;
            if(dis1 * a[i].s < a[j].s){
                v[a[i].ind].push_back(j) ;
            }
        }
        if(v[a[i].ind].size() == 0){
            ans[a[i].ind] = 0 ;
            continue ;
        }
//        for(auto p : v[a[i].ind]){
//            cout << a[p].ind << " " ;
//        }
//        cout << endl ;
        ll in = v[a[i].ind][0] ;
        bool is = 0 ;
        for(int j = 1 ; j < v[a[i].ind].size() ; j++){
            ll q = v[a[i].ind][j] ;
            ll dis1 = (a[i].x - a[q].x) * (a[i].x - a[q].x) + (a[i].y - a[q].y) * (a[i].y - a[q].y) ;
            ll dis2 = (a[i].x - a[in].x) * (a[i].x - a[in].x) + (a[i].y - a[in].y) * (a[i].y - a[in].y) ;
            if(dis1 * a[in].s == dis2 * a[q].s){
                is = 1 ;
            }
            else if(dis1 * a[in].s <= dis2 * a[q].s){
                is = 0 ;
                in = q ;
            }
        }
        if(is){
            ans[a[i].ind] = -1 ;
            continue ;
        }
        if(ans[a[in].ind] == 0){
            ans[a[i].ind] = a[in].ind + 1 ;
        }
        else{
            ans[a[i].ind] = ans[a[in].ind] ;
        }
    }
    for(int i = 0 ; i < n ; i++){
        if(ans[i] == 0){
            cout << "K" << endl ;
        }
        else if(ans[i] == -1){
            cout << "D" << endl ;
        }
        else{
            cout  << ans[i] << endl ;
        }
    }
    return 0 ;
}
/*
5
2 5 14
2 3 2
3 2 7
1 1 2
2 1 3

*/

Compilation message (stderr)

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

• Subtask 1: 100 / 100