| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 296261 | nvmdava | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
int d[5005][3];
vector<pair<int, int> > rh, lh;
int lo[5005], st[5005];
void solve(int con, int flip, vector<pair<int, int> >& v){
sort(v.begin(), v.end());
int r = -1;
for(auto& x : v){
if(r == -1 || getDistance(r, x.ss) != x.ff - lo[r]){
lo[r = x.ss] = x.ff;
st[r] = 1;
} else {
lo[x.ss] = lo[r] - (x.ff - lo[r]);
st[x.ss] = -1;
}
}
for(auto& x : v){
st[x.ss] *= flip;
lo[x.ss] = con + flip * lo[x.ss];
}
}
void findLocation(int N, int first, int location[], int stype[]){
int le, ri;
int n = N;
le = 0;
int tt = 2000000;
for(int i = 0; i < n; ++i){
if(le == i)
continue;
d[i][0] = getDistance(le, i);
if(d[i][0] < tt){
ri = i;
tt = d[i][0];
}
}
tt = 2000000;
for(int i = 0; i < n; ++i){
if(ri == i) continue;
d[i][1] = getDistance(ri, i);
if(d[i][1] < tt){
le = i;
tt = d[i][1];
}
}
lo[ri] = first + d[ri][0];
st[ri] = 1;
lo[le] = lo[ri] - d[le][1];
st[le] = -1;
d[0][0] = 2 * d[ri][0];
d[ri][1] = 2 * d[le][1];
for(int i = 0; i < n; ++i){
if(le == i || ri == i) continue;
if(d[i][0] == d[i][1] + d[ri][0]){
rh.push_back({d[i][1], i});
else
lh.push_back({d[i][0] - (d[ri][0] - d[le][1]), i});
}
solve(lo[le], 1, lh);
solve(lo[ri], -1, rh);
for(int i = 0; i < n; ++i){
location[i] = lo[i];
stype[i] = (st[i] == 1 ? 2 : 1);
}
}