#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
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++){
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5324 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 8 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 12 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 15 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 16 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 18 |
Correct |
5 ms |
6220 KB |
Output is correct |
| 19 |
Correct |
6 ms |
6816 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5068 KB |
Output is correct |
