# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
139096 |
2019-07-31T09:18:46 Z |
toonewbie |
Rail (IOI14_rail) |
C++17 |
|
87 ms |
888 KB |
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int n, int first, int l[], int t[]) {
l[0] = first;
t[0] = 1;
vector <pair <int, int>> v;
for (int i = 1; i < n; i++) {
v.push_back({getDistance(0, i), i});
}
sort(v.begin(), v.end());
l[v[0].second] = first + v[0].first;
t[v[0].second] = 2;
set <int> C, D;
C.insert(l[0]); D.insert(l[v[0].second]);
int L = 0, R = v[0].second;
for (int i = 1; i < v.size(); i++) {
int id = v[i].second;
int x = getDistance(id, L), y = getDistance(id, R);
int lcan = l[L] + x, rcan = l[R] - y, res;
auto it = --C.upper_bound(lcan);
if (y == lcan - *it + l[R] - *it) {
res = 1;
} else {
auto it = D.upper_bound(rcan);
if (it != D.end() && x == *it - rcan + *it - l[L]) {
res = 0;
} else {
if (v[i].first == 2 * l[v[0].second] - first - rcan) res = 0;
else res = 1;
}
}
if (res == 1) {
l[id] = lcan;
t[id] = 2;
D.insert(l[id]);
if (l[R] < l[id]) R = id;
} else {
l[id] = rcan;
t[id] = 1;
C.insert(l[id]);
if (l[L] > l[id]) L = id;
}
}
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); i++) {
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
252 KB |
Output is correct |
5 |
Correct |
2 ms |
252 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
420 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
712 KB |
Output is correct |
2 |
Correct |
84 ms |
888 KB |
Output is correct |
3 |
Correct |
86 ms |
744 KB |
Output is correct |
4 |
Correct |
84 ms |
732 KB |
Output is correct |
5 |
Correct |
84 ms |
756 KB |
Output is correct |
6 |
Correct |
86 ms |
888 KB |
Output is correct |
7 |
Correct |
85 ms |
760 KB |
Output is correct |
8 |
Correct |
84 ms |
864 KB |
Output is correct |
9 |
Correct |
85 ms |
764 KB |
Output is correct |
10 |
Correct |
86 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
716 KB |
Output is correct |
2 |
Correct |
85 ms |
776 KB |
Output is correct |
3 |
Correct |
84 ms |
836 KB |
Output is correct |
4 |
Correct |
85 ms |
764 KB |
Output is correct |
5 |
Correct |
84 ms |
764 KB |
Output is correct |
6 |
Correct |
85 ms |
760 KB |
Output is correct |
7 |
Correct |
85 ms |
772 KB |
Output is correct |
8 |
Correct |
85 ms |
768 KB |
Output is correct |
9 |
Correct |
85 ms |
772 KB |
Output is correct |
10 |
Correct |
86 ms |
760 KB |
Output is correct |
11 |
Correct |
84 ms |
888 KB |
Output is correct |
12 |
Correct |
84 ms |
800 KB |
Output is correct |
13 |
Correct |
86 ms |
760 KB |
Output is correct |
14 |
Correct |
84 ms |
888 KB |
Output is correct |
15 |
Correct |
84 ms |
760 KB |
Output is correct |
16 |
Correct |
85 ms |
732 KB |
Output is correct |
17 |
Correct |
85 ms |
768 KB |
Output is correct |
18 |
Correct |
85 ms |
760 KB |
Output is correct |
19 |
Correct |
87 ms |
756 KB |
Output is correct |
20 |
Correct |
85 ms |
888 KB |
Output is correct |