#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 ;
}
ll n , x[20000] , y[200009] , s[200009] , in[200009] , ans[2000009] ;
vector < ll > v[200009] ;
bool cmp(ll x , ll y){
return s[x] > s[y] ;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n ;
for(int i = 0 ; i < n ; i++){
cin >> x[i] >> y[i] >> s[i] ;
in[i] = i ;
}
sort(in , in + n , cmp) ;
for(int i = 0 ; i < n ; i++){
// cout << in[i] << endl ;
for(int j = 0; j < n ; j++){
if(in[i] == in[j])
continue ;
ll q = (x[in[i]] - x[in[j]]) * (x[in[i]] - x[in[j]]) + (y[in[i]] - y[in[j]]) * (y[in[i]] - y[in[j]]) ;
if(s[in[j]] > s[in[i]] * q){
v[in[i]].push_back(in[j]) ;
}
}
// for(auto p : v[in[i]]){
// cout << p << " " ;
// }
// cout << endl ;
if(v[in[i]].size() == 0){
ans[in[i]] = 0 ;
continue ;
}
ll ind = v[in[i]][0] ;
bool is = 0 ;
for(auto p : v[in[i]]){
if(p == ind)
continue ;
ll dis1 = (x[in[i]] - x[p]) * (x[in[i]] - x[p]) + (y[in[i]] - y[p]) * (y[in[i]] - y[p]) ;
ll dis2 = (x[in[i]] - x[ind]) * (x[in[i]] - x[ind]) + (y[in[i]] - y[ind]) * (y[in[i]] - y[ind]) ;
ll q = dis1 * s[ind] ;
ll q2 = dis2 * s[p] ;
// cout << q << " " << q2 << endl ;
if(q == q2){
is = 1 ;
}
if(q > q2){
ind = p ;
is = 0 ;
}
}
// cout << "ind is " << ind << endl ;
if(is){
ans[in[i]] = -1 ;
continue ;
}
else{
if(ans[ind] == 0)
ans[in[i]] = ind + 1 ;
else{
ans[in[i]] = ans[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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
5016 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
5144 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
5156 KB |
Output isn't correct |
| 5 |
Incorrect |
5 ms |
5068 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
5408 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
5028 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
5016 KB |
Output isn't correct |
| 9 |
Incorrect |
5 ms |
5028 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
5068 KB |
Output isn't correct |
| 11 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 12 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 13 |
Correct |
4 ms |
5004 KB |
Output is correct |
| 14 |
Incorrect |
4 ms |
5136 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
5020 KB |
Output isn't correct |
| 16 |
Incorrect |
5 ms |
5028 KB |
Output isn't correct |
| 17 |
Incorrect |
5 ms |
5068 KB |
Output isn't correct |
| 18 |
Incorrect |
9 ms |
6172 KB |
Output isn't correct |
| 19 |
Incorrect |
9 ms |
6816 KB |
Output isn't correct |
| 20 |
Incorrect |
6 ms |
5032 KB |
Output isn't correct |
