| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 585898 | SeDunion | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rail.h"
#include<iostream>
#include<set>
#include<vector>
using namespace std;
const int N = 5055;
const int inf = 1e9;
int n, d0[N];
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
vector<pair<int,int>>v;
for (int i = 1 ; i < n ; ++ i) {
d0[i] = getDistance(0, i);
v.emplace_back(d0[i], i);
}
sort(v.begin(), v.end());
int L = 0, R = v[0].second;
stype[0] = 1, location[0] = first;
stype[R] = 2, location[R] = first + v[0].first;
set<int>LL,RR;
LL.insert(location[L]);
RR.insert(location[R]);
int dlr = v[0].first;
for (int i = 1 ; i < (int)v.size() ; ++ i) {
int di = v[i].first, k = v[i].second;
int dl = getDistance(L, k);
int dr = getDistance(R, k);
int X = location[L];
int Y = location[R];
int Z = Y - dr;
if (Z < X) {
int D = X - Z;
int C = dl - D;
if (C % 2 == 0) {
C /= 2;
C += X;
if (*RR.lower_bound(X) == C) {
stype[k] = 1;
location[k] = Z;
L = k;
continue;
}
}
} else {
int D = Z - X;
int C = dl - D;
if (C % 2 == 0) {
C /= 2;
C += X;
if (*RR.lower_bound(Z) == C) {
stype[k] = 1;
location[k] = Z;
continue;
}
}
}
Z = X + dl;
if (Y < Z) {
int D = Z - Y;
int C = dr - D;
if (C % 2 == 0) {
C /= 2;
C = Y - C;
if (*prev(LL.upper_bound(Y)) == C) {
stype[k] = 2;
location[k] = Z;
R = k;
continue;
}
}
} else {
int D = Y - Z;
int C = dr - D;
if (C % 2 == 0) {
C /= 2;
C = Y - C;
if (*prev(LL.upper_bound(Z)) == C) {
stype[k] = 2;
location[k] = Z;
continue;
}
}
}
}
for (int i = 0 ; i < n ; ++ i) {
// cout << stype[i] << " " << location[i] << endl;
}
}