# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
38854 |
2018-01-07T10:10:40 Z |
14kg |
Rail (IOI14_rail) |
C++11 |
|
125 ms |
836 KB |
#include "rail.h"
#include <algorithm>
#define N 5001
#define INF 999999999
using namespace std;
int n, zd[N], zero;
int rd[N], rw, r_num, lw, l_num;
int L_len, R_len, S_len, S[N];
pair<int, int> L[N], R[N];
void findLocation(int _n, int _zero, int out1[], int out2[]) {
int temp = INF, len;
bool check;
n = _n, zero = _zero;
for (int i = 1; i < n; i++) {
zd[i] = getDistance(0, i);
if (temp > zd[i]) {
temp = zd[i], r_num = i;
rw = zero + temp;
}
}
temp = rw - zero, lw = zero;
for (int i = 1; i < n; i++)
if (i != r_num) {
rd[i] = getDistance(r_num, i);
if (temp > rd[i])
temp = rd[i], lw = rw - rd[i], l_num = i;
}
out1[0] = zero, out2[0] = 1;
out1[r_num] = rw, out2[r_num] = 2;
out1[l_num] = lw, out2[l_num] = 1;
for (int i = 1; i < n; i++)
if (i != r_num && i != l_num) {
if (rd[i] - (rw - lw) == zd[i] - (lw - zero)) {
out1[i] = zero + zd[i], out2[i] = 2;
R[++R_len] = { out1[i],i };
}
else if (rd[i] + rw - zero == zd[i]) {
out1[i] = rw - rd[i], out2[i] = 1;
L[++L_len] = { -out1[i],i };
}
}
L[++L_len] = { -zero,0 };
sort(L + 1, L + L_len + 1), sort(R + 1, R + R_len + 1);
temp = r_num, S[S_len = 1] = r_num;
for (int i = 1; i <= R_len; i++) {
len = getDistance(temp, R[i].second), check = true;
for (int j = S_len; j >= 1 && check; j--)
if (zd[R[i].second] == zd[temp] + len - (out1[temp] - S[j]) * 2)
out1[R[i].second] = out1[temp] - len, out2[R[i].second] = 1, check = false;
if (check) temp = R[i].second, S[++S_len] = out1[temp];
}
temp = l_num, S[S_len = 1] = l_num;
for (int i = 1; i <= L_len; i++) {
len = getDistance(temp, L[i].second), check = true;
for (int j = S_len; j >= 1 && check; j--)
if (rd[L[i].second] == rd[temp] + len - (S[j] - out1[temp]) * 2)
out1[L[i].second] = out1[temp] + len, out2[L[i].second] = 2, check = false;
if (check) temp = L[i].second, S[++S_len] = out1[temp];
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
320 KB |
Output is correct |
2 |
Correct |
3 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
484 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
564 KB |
Output is correct |
6 |
Correct |
2 ms |
564 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
3 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
620 KB |
Output is correct |
10 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
620 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
2 ms |
620 KB |
Output is correct |
4 |
Correct |
2 ms |
620 KB |
Output is correct |
5 |
Correct |
2 ms |
620 KB |
Output is correct |
6 |
Correct |
2 ms |
620 KB |
Output is correct |
7 |
Correct |
2 ms |
620 KB |
Output is correct |
8 |
Correct |
2 ms |
620 KB |
Output is correct |
9 |
Correct |
2 ms |
620 KB |
Output is correct |
10 |
Correct |
2 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
832 KB |
Output is correct |
2 |
Correct |
86 ms |
832 KB |
Output is correct |
3 |
Correct |
85 ms |
832 KB |
Output is correct |
4 |
Correct |
97 ms |
832 KB |
Output is correct |
5 |
Correct |
93 ms |
832 KB |
Output is correct |
6 |
Correct |
93 ms |
836 KB |
Output is correct |
7 |
Correct |
107 ms |
836 KB |
Output is correct |
8 |
Correct |
109 ms |
836 KB |
Output is correct |
9 |
Correct |
93 ms |
836 KB |
Output is correct |
10 |
Correct |
116 ms |
836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
836 KB |
Output is correct |
2 |
Correct |
100 ms |
836 KB |
Output is correct |
3 |
Correct |
93 ms |
836 KB |
Output is correct |
4 |
Correct |
94 ms |
836 KB |
Output is correct |
5 |
Correct |
90 ms |
836 KB |
Output is correct |
6 |
Correct |
125 ms |
836 KB |
Output is correct |
7 |
Correct |
94 ms |
836 KB |
Output is correct |
8 |
Correct |
93 ms |
836 KB |
Output is correct |
9 |
Correct |
98 ms |
836 KB |
Output is correct |
10 |
Correct |
111 ms |
836 KB |
Output is correct |
11 |
Correct |
90 ms |
836 KB |
Output is correct |
12 |
Correct |
86 ms |
836 KB |
Output is correct |
13 |
Correct |
93 ms |
836 KB |
Output is correct |
14 |
Correct |
94 ms |
836 KB |
Output is correct |
15 |
Correct |
96 ms |
836 KB |
Output is correct |
16 |
Correct |
119 ms |
836 KB |
Output is correct |
17 |
Correct |
107 ms |
836 KB |
Output is correct |
18 |
Correct |
94 ms |
836 KB |
Output is correct |
19 |
Correct |
111 ms |
836 KB |
Output is correct |
20 |
Correct |
107 ms |
836 KB |
Output is correct |