| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 829848 | FatihSolak | 원 고르기 (APIO18_circle_selection) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 300005
using namespace std;
int x[N],y[N],c[N];
int ans[N];
int tm[N];
void solve(){
int n;
cin >> n;
vector<int> ord;
for(int i = 1;i<=n;i++){
cin >> x[i] >> y[i] >> c[i];
ord.push_back(i);
}
sort(ord.begin(),ord.end(),[&](int a,int b){
if(c[a] == c[b])
return a < b;
return c[a] > c[b];
});
set<pair<long long,int>> s[3][3][3];
set<int> alive;
int cnt = 0;
for(auto u:ord){
int num = -1;
vector<int> cand;
for(auto xx:alive)
cand.push_back(xx);
// for(int i = -1;i<=1;i++){
// for(int j = -1;j<=1;j++){
// for(int k = -1;k<=1;k++){
// long long sum = 0;
// sum += i * x[u];
// sum += j * y[u];
// sum += k * c[u];
// auto it = s[i + 1][j + 1][k + 1].lower_bound({sum,0});
// if(it != s[i+1][j+1][k+1].end()){
// cand.push_back(it->second);
// }
// if(it != s[i+1][j+1][k+1].begin()){
// cand.push_back(prev(it)->second);
// }
// }
// }
// }
for(auto cc:cand){
long long val1 = (long long)(c[u] + c[cc]) *(c[u] + c[cc]);
long long val2 = (long long)(x[u] - x[cc]) *(x[u] - x[cc])
+ (long long)(y[u] - y[cc]) *(y[u] - y[cc]);
if(val2 <= val1){
if(num == -1 || tm[u] < tm[num])
num = cc;
}
}
if(num == -1){
alive.insert(u);
tm[u] =cnt;
ans[u] = u;
for(int i = -1;i<=1;i++){
for(int j = -1;j<=1;j++){
for(int k = -1;k<=1;k++){
long long sum = 0;
sum += i * x[u];
sum += j * y[u];
sum += k * c[u];
s[i + 1][j + 1][k + 1].insert({sum,u});
}
}
}
}
else ans[u] = num;
}
for(int i = 1;i<=n;i++){
cout << ans[i] << ' ';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while(t--){
solve();
}
}