| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 301648 |
2020-09-18T05:42:30 Z |
kevinsogo |
Rail (IOI14_rail) |
C++17 |
|
424 ms |
768 KB |
#include <bits/stdc++.h>
using namespace std;
#include "rail.h"
#define C 1
#define D 2
#define EMPTY -1
void findLocation(int n, int loc, int locs[], int typs[]) {
for (int i = 0; i < n; i++) typs[i] = EMPTY;
locs[0] = loc;
typs[0] = C;
if (n >= 2) {
vector<int> d0(n);
int xr = -1;
for (int i = 0; i < n; i++) {
if (i != 0) {
d0[i] = getDistance(0, i);
if (xr == -1 || d0[xr] > d0[i]) xr = i;
}
}
locs[xr] = locs[0] + d0[xr];
typs[xr] = D;
vector<int> dxr(n);
int xl = -1;
for (int i = 0; i < n; i++) {
if (i != xr) {
dxr[i] = getDistance(xr, i);
if (xl == -1 || dxr[xl] > dxr[i]) xl = i;
}
}
locs[xl] = locs[xr] - dxr[xl];
typs[xl] = C;
vector<int> dxl(n), rseq, lseq;
for (int i = 0; i < n; i++) {
if (i != xl) {
dxl[i] = i == 0 ? d0[xl] : d0[i] - (dxr[0] - dxr[xl]);
}
if (typs[i] == EMPTY) {
(dxl[i] < dxr[i] ? rseq : lseq).push_back(i);
}
}
for (int it = 0; it < 2; it++) {
swap(lseq, rseq);
swap(xl, xr);
swap(dxl, dxr);
for (int i = 0; i < n; i++) {
if (typs[i] != EMPTY) {
typs[i] = typs[i] == C ? D : C;
locs[i] = -locs[i];
}
}
vector<int>& seq = rseq;
sort(seq.begin(), seq.end(), [&dxl](int i, int j) { return dxl[i] < dxl[j]; });
for (int i : seq) {
int rightmost_c = xl, rightmost_d = xr;
for (int i : seq) {
if (typs[i] == C) {
if (locs[rightmost_c] < locs[i]) rightmost_c = i;
}
if (typs[i] == D) {
if (locs[rightmost_d] < locs[i]) rightmost_d = i;
}
}
assert(locs[rightmost_c] < locs[rightmost_d]);
int dr = getDistance(i, rightmost_d);
auto good = [&](int pos) {
for (int i = 0; i < n; i++) {
if (typs[i] != EMPTY && locs[i] == pos) return false;
}
if (pos > locs[rightmost_d]) {
if (dxl[i] != pos - locs[xl])
return false;
int possible_c = pos + locs[rightmost_d] - dr;
assert(possible_c % 2 == 0);
possible_c >>= 1;
if (!(locs[rightmost_c] <= possible_c && possible_c < locs[rightmost_d]))
return false;
for (int j = 0; j < n; j++) {
if (typs[j] == D && locs[j] == possible_c) return false;
}
} else {
assert(pos < locs[rightmost_d]);
int rd = rightmost_d;
for (int j = 0; j < n; j++) {
if (typs[j] == D && pos < locs[j] && locs[j] < locs[rd]) rd = j;
}
if (dxl[i] != locs[rd] - pos + locs[rd] - locs[xl])
return false;
if (dr != locs[rightmost_d] - pos)
return false;
}
return true;
};
for (int pos : {locs[xl] + dxl[i], locs[rightmost_d] - dr}) {
if (good(pos)) {
assert(typs[i] == EMPTY);
typs[i] = (locs[i] = pos) < locs[rightmost_d] ? C : D;
}
}
assert(typs[i] != EMPTY);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
416 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
372 ms |
632 KB |
Output is correct |
| 2 |
Correct |
372 ms |
768 KB |
Output is correct |
| 3 |
Correct |
357 ms |
760 KB |
Output is correct |
| 4 |
Correct |
351 ms |
760 KB |
Output is correct |
| 5 |
Correct |
382 ms |
668 KB |
Output is correct |
| 6 |
Correct |
418 ms |
632 KB |
Output is correct |
| 7 |
Correct |
375 ms |
632 KB |
Output is correct |
| 8 |
Correct |
360 ms |
760 KB |
Output is correct |
| 9 |
Correct |
359 ms |
632 KB |
Output is correct |
| 10 |
Correct |
361 ms |
648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
373 ms |
632 KB |
Output is correct |
| 2 |
Correct |
354 ms |
644 KB |
Output is correct |
| 3 |
Correct |
362 ms |
664 KB |
Output is correct |
| 4 |
Correct |
354 ms |
632 KB |
Output is correct |
| 5 |
Correct |
379 ms |
664 KB |
Output is correct |
| 6 |
Correct |
424 ms |
636 KB |
Output is correct |
| 7 |
Correct |
375 ms |
632 KB |
Output is correct |
| 8 |
Correct |
360 ms |
632 KB |
Output is correct |
| 9 |
Correct |
367 ms |
580 KB |
Output is correct |
| 10 |
Correct |
362 ms |
632 KB |
Output is correct |
| 11 |
Correct |
388 ms |
632 KB |
Output is correct |
| 12 |
Correct |
383 ms |
760 KB |
Output is correct |
| 13 |
Correct |
361 ms |
760 KB |
Output is correct |
| 14 |
Correct |
381 ms |
644 KB |
Output is correct |
| 15 |
Correct |
368 ms |
664 KB |
Output is correct |
| 16 |
Correct |
361 ms |
644 KB |
Output is correct |
| 17 |
Correct |
385 ms |
536 KB |
Output is correct |
| 18 |
Correct |
376 ms |
640 KB |
Output is correct |
| 19 |
Correct |
366 ms |
644 KB |
Output is correct |
| 20 |
Correct |
375 ms |
760 KB |
Output is correct |
