# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
687660 |
2023-01-26T18:19:52 Z |
Alcabel |
Rail (IOI14_rail) |
C++17 |
|
85 ms |
588 KB |
#include <rail.h>
#include <bits/stdc++.h>
using namespace std;
const int C = 1, D = 2;
void findLocation(int n, int first, int location[], int stype[]) {
for (int i = 0; i < n; ++i) {
location[i] = -1, stype[i] = -1;
}
location[0] = first, stype[0] = C;
vector<int> dFirst(n), dNxt(n);
dFirst[0] = 0;
for (int i = 1; i < n; ++i) {
dFirst[i] = getDistance(0, i);
}
int nxt = min_element(dFirst.begin() + 1, dFirst.end()) - dFirst.begin();
location[nxt] = location[0] + dFirst[nxt];
stype[nxt] = D;
dNxt[0] = dFirst[nxt], dNxt[nxt] = 0;
for (int i = 1; i < n; ++i) {
if (i != nxt) {
dNxt[i] = getDistance(nxt, i);
}
}
vector<int> left, right, x;
for (int i = 1; i < n; ++i) {
if (i != nxt) {
if (dFirst[i] == dNxt[i] + dFirst[nxt]) {
left.emplace_back(i);
} else {
right.emplace_back(i);
}
}
}
sort(left.begin(), left.end(), [&](const int& A, const int& B) {
return dNxt[A] < dNxt[B];
});
for (const int& y : left) {
if (dNxt[y] <= dNxt[0]) {
location[y] = location[nxt] - dNxt[y];
stype[y] = C;
} else if (!x.empty()) {
bool isC = true;
int curD = getDistance(y, x.back());
for (const int& owner : x) {
if (curD == dNxt[y] - dNxt[owner] + dNxt[x.back()] - dNxt[owner]) {
isC = false;
location[y] = location[owner] + dNxt[y] - dNxt[owner];
stype[y] = D;
break;
}
}
if (isC) {
location[y] = location[nxt] - dNxt[y];
stype[y] = C;
x.emplace_back(y);
}
} else {
location[y] = location[nxt] - dNxt[y];
stype[y] = C;
x.emplace_back(y);
}
}
sort(right.begin(), right.end(), [&](const int& A, const int& B) {
return dFirst[A] < dFirst[B];
});
x.clear();
for (const int& y : right) {
assert(location[y] == -1);
if (!x.empty()) {
bool isD = true;
int curD = getDistance(y, x.back());
for (const int& owner : x) {
if (curD == dFirst[y] - dFirst[owner] + dFirst[x.back()] - dFirst[owner]) {
isD = false;
location[y] = location[owner] - (dFirst[y] - dFirst[owner]);
stype[y] = C;
break;
}
}
if (isD) {
location[y] = location[0] + dFirst[y];
stype[y] = D;
x.emplace_back(y);
}
} else {
location[y] = location[0] + dFirst[y];
stype[y] = D;
x.emplace_back(y);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
380 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
388 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
496 KB |
Output is correct |
2 |
Correct |
77 ms |
496 KB |
Output is correct |
3 |
Correct |
75 ms |
500 KB |
Output is correct |
4 |
Correct |
73 ms |
500 KB |
Output is correct |
5 |
Correct |
72 ms |
516 KB |
Output is correct |
6 |
Correct |
74 ms |
588 KB |
Output is correct |
7 |
Correct |
72 ms |
500 KB |
Output is correct |
8 |
Correct |
70 ms |
500 KB |
Output is correct |
9 |
Correct |
73 ms |
512 KB |
Output is correct |
10 |
Correct |
70 ms |
500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
500 KB |
Output is correct |
2 |
Correct |
72 ms |
504 KB |
Output is correct |
3 |
Correct |
69 ms |
496 KB |
Output is correct |
4 |
Correct |
76 ms |
500 KB |
Output is correct |
5 |
Correct |
85 ms |
504 KB |
Output is correct |
6 |
Correct |
74 ms |
588 KB |
Output is correct |
7 |
Correct |
71 ms |
512 KB |
Output is correct |
8 |
Correct |
70 ms |
500 KB |
Output is correct |
9 |
Correct |
76 ms |
508 KB |
Output is correct |
10 |
Correct |
71 ms |
508 KB |
Output is correct |
11 |
Correct |
72 ms |
588 KB |
Output is correct |
12 |
Correct |
72 ms |
508 KB |
Output is correct |
13 |
Correct |
74 ms |
508 KB |
Output is correct |
14 |
Correct |
71 ms |
512 KB |
Output is correct |
15 |
Correct |
74 ms |
588 KB |
Output is correct |
16 |
Correct |
75 ms |
516 KB |
Output is correct |
17 |
Correct |
75 ms |
508 KB |
Output is correct |
18 |
Correct |
69 ms |
512 KB |
Output is correct |
19 |
Correct |
72 ms |
512 KB |
Output is correct |
20 |
Correct |
76 ms |
508 KB |
Output is correct |