# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
49384 |
2018-05-28T07:07:43 Z |
imeimi2000 |
Rail (IOI14_rail) |
C++17 |
|
143 ms |
916 KB |
#include "rail.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 5000;
int n;
int d0[MAXN];
int d1[MAXN];
int rd[MAXN];
int *l, *t;
void calc(vector<int> &ps, int s) {
sort(ps.begin(), ps.end(), [&](int i, int j) { return rd[i] < rd[j]; });
set<int> mp;
l[ps[0]] = l[s] + rd[ps[0]];
t[ps[0]] = 2;
int mx = ps[0];
mp.insert(l[mx] << 1);
for (int i = 1; i < ps.size(); ++i) {
int fn = (l[mx] << 1) + rd[ps[i]] - rd[mx] - getDistance(ps[i], mx);
if (mp.find(fn) != mp.end()) {
l[ps[i]] = fn - rd[ps[i]] - l[s];
t[ps[i]] = 1;
}
else {
l[ps[i]] = l[s] + rd[ps[i]];
t[ps[i]] = 2;
mp.insert(l[ps[i]] << 1);
mx = ps[i];
}
}
}
void findLocation(int N, int f, int _l[], int _t[]) {
n = N;
l = _l;
t = _t;
int mn = 1;
for (int i = 1; i < n; ++i) {
d0[i] = getDistance(0, i);
if (d0[i] < d0[mn]) mn = i;
}
d1[0] = d0[mn];
vector<int> vt1, vt2;
rd[0] = rd[mn] = d1[0];
vt1.push_back(0);
vt2.push_back(mn);
for (int i = 1; i < n; ++i) {
if (mn == i) continue;
d1[i] = getDistance(mn, i);
if (d0[i] == d1[i] + d1[0]) vt1.push_back(i), rd[i] = d1[i];
else vt2.push_back(i), rd[i] = d0[i];
}
l[0] = f;
t[0] = 1;
calc(vt2, 0);
l[mn] = -(f + d1[0]);
t[mn] = 1;
calc(vt1, mn);
l[mn] = -l[mn];
t[mn] = 2;
for (int i : vt1) {
l[i] = -l[i];
t[i] ^= 3;
}
}
Compilation message
rail.cpp: In function 'void calc(std::vector<int>&, int)':
rail.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < ps.size(); ++i) {
~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
356 KB |
Output is correct |
4 |
Correct |
2 ms |
432 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
540 KB |
Output is correct |
8 |
Correct |
2 ms |
616 KB |
Output is correct |
9 |
Correct |
2 ms |
616 KB |
Output is correct |
10 |
Correct |
2 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
760 KB |
Output is correct |
2 |
Correct |
2 ms |
760 KB |
Output is correct |
3 |
Correct |
2 ms |
760 KB |
Output is correct |
4 |
Correct |
2 ms |
760 KB |
Output is correct |
5 |
Correct |
2 ms |
760 KB |
Output is correct |
6 |
Correct |
2 ms |
760 KB |
Output is correct |
7 |
Correct |
2 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
2 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
844 KB |
Output is correct |
2 |
Correct |
95 ms |
844 KB |
Output is correct |
3 |
Correct |
94 ms |
844 KB |
Output is correct |
4 |
Correct |
88 ms |
844 KB |
Output is correct |
5 |
Correct |
88 ms |
892 KB |
Output is correct |
6 |
Correct |
87 ms |
892 KB |
Output is correct |
7 |
Correct |
88 ms |
892 KB |
Output is correct |
8 |
Correct |
90 ms |
892 KB |
Output is correct |
9 |
Correct |
87 ms |
892 KB |
Output is correct |
10 |
Correct |
100 ms |
892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
892 KB |
Output is correct |
2 |
Correct |
100 ms |
892 KB |
Output is correct |
3 |
Correct |
98 ms |
892 KB |
Output is correct |
4 |
Correct |
102 ms |
892 KB |
Output is correct |
5 |
Correct |
90 ms |
892 KB |
Output is correct |
6 |
Correct |
91 ms |
892 KB |
Output is correct |
7 |
Correct |
91 ms |
916 KB |
Output is correct |
8 |
Correct |
114 ms |
916 KB |
Output is correct |
9 |
Correct |
92 ms |
916 KB |
Output is correct |
10 |
Correct |
91 ms |
916 KB |
Output is correct |
11 |
Correct |
94 ms |
916 KB |
Output is correct |
12 |
Correct |
112 ms |
916 KB |
Output is correct |
13 |
Correct |
143 ms |
916 KB |
Output is correct |
14 |
Correct |
94 ms |
916 KB |
Output is correct |
15 |
Correct |
93 ms |
916 KB |
Output is correct |
16 |
Correct |
94 ms |
916 KB |
Output is correct |
17 |
Correct |
90 ms |
916 KB |
Output is correct |
18 |
Correct |
91 ms |
916 KB |
Output is correct |
19 |
Correct |
91 ms |
916 KB |
Output is correct |
20 |
Correct |
85 ms |
916 KB |
Output is correct |