# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
579583 |
2022-06-19T11:55:42 Z |
elazarkoren |
Rail (IOI14_rail) |
C++17 |
|
87 ms |
588 KB |
#include "rail.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 5005;
int dist0[MAX_N], dist1[MAX_N];
void findLocation(int n, int first, int location[], int stype[]) {
int closest = 1;
for (int i = 1; i < n; i++) {
dist0[i] = getDistance(0, i);
if (dist0[i] < dist0[closest]) closest = i;
}
location[0] = first, stype[0] = 1;
location[closest] = dist0[closest] + first, stype[closest] = 2;
vi ind_l, ind_r;
dist1[0] = dist0[closest];
for (int i = 1; i < n; i++) {
if (i == closest) continue;
dist1[i] = getDistance(closest, i);
if (dist0[i] != dist0[closest] + dist1[i]) {
ind_r.push_back(i);
} else if (dist1[i] > dist1[0]) {
ind_l.push_back(i);
} else {
location[i] = location[closest] - dist1[i];
stype[i] = 1;
}
}
if (!ind_r.empty()) {
sort(all(ind_r), [&](int i, int j) {
return dist0[i] < dist0[j];
});
int last = ind_r[0];
location[last] = first + dist0[last];
stype[last] = 2;
vi v = {last};
for (int i : ind_r) {
if (i == last) continue;
int d = getDistance(last, i);
int x1 = location[last] - d;
int j;
for (int k : v) {
if (location[k] > x1) {
j = k;
break;
}
}
if (location[last] - (dist0[last] + d - dist0[i]) / 2 != location[j]) {
// if (getDistance(j, i) + dist0[j] != dist0[i]) {
stype[i] = 2;
location[i] = dist0[i] + first;
last = i;
v.push_back(i);
} else {
stype[i] = 1;
location[i] = first + 2 * dist0[j] - dist0[i];
}
}
}
if (!ind_l.empty()) {
sort(all(ind_l), [&](int i, int j) {
return dist1[i] < dist1[j];
});
int last = ind_l[0];
location[last] = location[closest] - dist1[last];
stype[last] = 1;
vi v = {last};
for (int i : ind_l) {
if (i == last) continue;
int d = getDistance(last, i);
int x1 = location[last] + d;
int j;
for (int k : v) {
if (location[k] < x1) {
j = k;
break;
}
}
if (location[last] + (dist1[last] + d - dist1[i]) / 2 != location[j]) {
// if (getDistance(j, i) + dist1[j] != dist1[i]) {
stype[i] = 1;
location[i] = location[closest] - dist1[i];
last = i;
v.push_back(i);
} else {
stype[i] = 2;
location[i] = location[closest] - (2 * dist1[j] - dist1[i]);
}
}
}
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:91:79: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
91 | if (location[last] + (dist1[last] + d - dist1[i]) / 2 != location[j]) {
| ^
rail.cpp:60:79: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
60 | if (location[last] - (dist0[last] + d - dist0[i]) / 2 != location[j]) {
| ^
# |
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 |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 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 |
0 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 |
0 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 |
75 ms |
468 KB |
Output is correct |
2 |
Correct |
75 ms |
588 KB |
Output is correct |
3 |
Correct |
80 ms |
508 KB |
Output is correct |
4 |
Correct |
69 ms |
508 KB |
Output is correct |
5 |
Correct |
70 ms |
508 KB |
Output is correct |
6 |
Correct |
73 ms |
504 KB |
Output is correct |
7 |
Correct |
79 ms |
572 KB |
Output is correct |
8 |
Correct |
73 ms |
516 KB |
Output is correct |
9 |
Correct |
68 ms |
588 KB |
Output is correct |
10 |
Correct |
77 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
472 KB |
Output is correct |
2 |
Correct |
87 ms |
516 KB |
Output is correct |
3 |
Correct |
68 ms |
512 KB |
Output is correct |
4 |
Correct |
68 ms |
524 KB |
Output is correct |
5 |
Correct |
73 ms |
512 KB |
Output is correct |
6 |
Correct |
73 ms |
508 KB |
Output is correct |
7 |
Correct |
77 ms |
512 KB |
Output is correct |
8 |
Correct |
68 ms |
524 KB |
Output is correct |
9 |
Correct |
69 ms |
520 KB |
Output is correct |
10 |
Correct |
69 ms |
528 KB |
Output is correct |
11 |
Correct |
76 ms |
524 KB |
Output is correct |
12 |
Correct |
73 ms |
504 KB |
Output is correct |
13 |
Correct |
73 ms |
512 KB |
Output is correct |
14 |
Correct |
69 ms |
508 KB |
Output is correct |
15 |
Correct |
71 ms |
512 KB |
Output is correct |
16 |
Correct |
72 ms |
512 KB |
Output is correct |
17 |
Correct |
72 ms |
528 KB |
Output is correct |
18 |
Correct |
69 ms |
516 KB |
Output is correct |
19 |
Correct |
71 ms |
512 KB |
Output is correct |
20 |
Correct |
72 ms |
516 KB |
Output is correct |