| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 599896 | 8e7 | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Challenge: Accepted
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 5005
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;
void findLocation(int N, int first, int location[], int stype[]) {
vector<int> dl(N, 0), dr(N, 0);
dl[0] = inf;
for (int i = 1;i < N;i++) {
dl[i] = getDistance(0, i);
}
location[0] = first;
stype[0] = 1;
if (N == 1) return;
int rid = min_element(dl.begin(), dl.end()) - dl.begin();
dr[rid] = inf;
int llen = dl[rid];
location[rid] = first + dl[rid];
stype[rid] = 2;
vector<pii> vl, vr;
stype[i] = 1;
} else {
vl.push_back({dr[i], i});
}
}
}
}
int lid = min_element(dr.begin(), dr.end()) - dr.begin();
for (int i = 0;i < N;i++) {
if (i == rid) dl[i] = dr[lid];
else if (i && dl[i] - dr[i] != llen) {
debug("rig", i);
dl[i] = dr[i] - dr[lid];
vr.push_back({dl[i], i});
}
}
debug("lid", lid, "rid", rid);
sort(vl.begin(), vl.end()), sort(vr.begin(), vr.end());
int lef = 0;
for (auto [dis, id]:vl) {
int p = getDistance(lef, id);
if (dis - p == dr[lef]) {
location[id] = location[lef] + p;
stype[id] = 2;
} else {
location[id] = location[rid] - dis;
stype[id] = 1;
lef = id;
}
}
int rig = rid;
for (auto [dis, id]:vr) {
int p = getDistance(rig, id);
if (dis - p == dl[rig]) {
location[id] = location[rig] - p;
stype[id] = 1;
} else {
location[id] = location[lid] + dis;
stype[id] = 2;
rig = id;
}
}
pary(stype,stype + N);
pary(location, location + N);
}