# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
548289 |
2022-04-12T21:54:52 Z |
sidon |
Rail (IOI14_rail) |
C++17 |
|
81 ms |
772 KB |
#include <bits/stdc++.h>
using namespace std;
#include "rail.h"
void findLocation(int N, int o, int* x, int* t) {
int d[N] {}, dC[N], byD[N - 1];
map<int, int> g;
t[0] = g[x[0] = o] = 1;
for(int v = 1; v < N; ++v) {
d[v] = getDistance(0, v);
byD[v-1] = v;
}
int c = min_element(d + 1, d + N) - d, rD = c, lD = c, rC {}, lC {}, sp {0};
t[c] = g[x[c] = o + d[c]] = 2;
for(int v = 0; v < N; ++v) {
dC[v] = getDistance(c, v);
if(v != c && dC[v] < dC[sp]) sp = v;
}
sort(byD, byD + N - 1, [&](const int &i, const int &j) {
if(d[i] == d[j]) return dC[i] < dC[j];
return d[i] < d[j];
});
for(const int &v : byD) if(v != c) {
int z = dC[v];
if(z > (d[v] - (d[c] - dC[sp]))) {
int y = getDistance(rD, v);
int xU = (x[rD] + (o + d[v]) - y) / 2;
if((!(((x[rD] + (o + d[v]) - y)) & 1) && g[xU] == 2)) x[v] = x[rD] - y , t[v] = 1;
else x[rD = v] = o + d[v], t[v] = 2;
} else {
int y = getDistance(lC, v);
if(!lC) x[v] = x[c] - z, t[v] = 1;
else {
int xU = (y + x[lC] + (x[c] - z)) / 2;
if(!(((y + x[lC] + (x[c] - z))) & 1) && g[xU] == 1) x[v] = x[lC] + y, t[v] = 2;
else x[v] = x[c] - z, t[v] = 1;
}
}
if(t[v] < 2) {
if(x[v] > x[rC]) rC = v;
if(x[v] < x[lC]) lC = v;
} else if(x[v] < x[lD]) lD = v;
g[x[v]] = t[v];
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
384 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 |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
380 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 |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
340 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 |
340 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 |
73 ms |
756 KB |
Output is correct |
2 |
Correct |
67 ms |
756 KB |
Output is correct |
3 |
Correct |
69 ms |
748 KB |
Output is correct |
4 |
Correct |
69 ms |
772 KB |
Output is correct |
5 |
Correct |
73 ms |
772 KB |
Output is correct |
6 |
Correct |
71 ms |
756 KB |
Output is correct |
7 |
Correct |
71 ms |
760 KB |
Output is correct |
8 |
Correct |
66 ms |
716 KB |
Output is correct |
9 |
Correct |
66 ms |
752 KB |
Output is correct |
10 |
Correct |
70 ms |
752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
768 KB |
Output is correct |
2 |
Correct |
73 ms |
752 KB |
Output is correct |
3 |
Correct |
72 ms |
764 KB |
Output is correct |
4 |
Correct |
66 ms |
716 KB |
Output is correct |
5 |
Correct |
69 ms |
768 KB |
Output is correct |
6 |
Correct |
67 ms |
760 KB |
Output is correct |
7 |
Correct |
67 ms |
688 KB |
Output is correct |
8 |
Correct |
81 ms |
756 KB |
Output is correct |
9 |
Correct |
69 ms |
752 KB |
Output is correct |
10 |
Correct |
66 ms |
764 KB |
Output is correct |
11 |
Correct |
66 ms |
756 KB |
Output is correct |
12 |
Correct |
69 ms |
764 KB |
Output is correct |
13 |
Correct |
73 ms |
748 KB |
Output is correct |
14 |
Correct |
67 ms |
752 KB |
Output is correct |
15 |
Correct |
66 ms |
756 KB |
Output is correct |
16 |
Correct |
65 ms |
752 KB |
Output is correct |
17 |
Correct |
67 ms |
756 KB |
Output is correct |
18 |
Correct |
72 ms |
752 KB |
Output is correct |
19 |
Correct |
66 ms |
716 KB |
Output is correct |
20 |
Correct |
67 ms |
760 KB |
Output is correct |