# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
949690 |
2024-03-19T15:15:16 Z |
Pikachu |
Rail (IOI14_rail) |
C++17 |
|
48 ms |
1144 KB |
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
template<typename T>
inline bool mini(T &x, const T &val)
{
if (x > val) return x = val, true;
return false;
}
template<typename T>
inline bool maxi(T &x, const T &val)
{
if (x < val) return x = val, true;
return false;
}
void findLocation(int n, int first, int location[], int stype[])
{
for (int i = 0; i < n; i++) location[i] = -1;
location[0] = first;
stype[0] = 1;
vector<pair<int,int> > d;
for (int i = 1; i < n; i++) {
d.push_back({getDistance(0, i), i});
}
sort(d.begin(), d.end());
int second = first + d[0].first;
location[d[0].second] = second;
stype[d[0].second] = 2;
int l = 0, r = d[0].second;
set<int> mp[4];
mp[1].insert(first);
mp[2].insert(second);
for (int i = 1; i < n - 1; i++) {
int d0 = d[i].first;
int id = d[i].second;
int dl = getDistance(l, id);
int dr = getDistance(r, id);
bool done = false;
if (!done && location[l] + dl < location[r]) {
int nloc = location[l] + dl;
int dak = (dr - (location[r] - nloc));
if (dak % 2 == 0) {
int tmp = nloc - dak / 2;
auto it = mp[1].lower_bound(nloc);
if (it != mp[1].begin() && *(--it) == tmp) {
if ((nloc > first && d0 == nloc - first)
|| (nloc < first && d0 == 2 * second + nloc - first - 2 * (*it))) {
location[id] = nloc;
stype[id] = 2;
done = true;
}
}
}
}
if (!done && location[r] - dr > location[l]) {
int nloc = location[r] - dr;
int dak = (dl - (nloc - location[l]));
if (dak % 2 == 0) {
int tmp = nloc + dak / 2;
auto it = mp[2].upper_bound(nloc);
if (it != mp[2].end() && *it == tmp) {
if ((nloc < first && d0 == 2 * second - first - nloc)
|| (nloc > first && d0 == 2 * (*it) - first - nloc)) {
location[id] = nloc;
stype[id] = 1;
done = true;
}
}
}
}
if (!done && location[l] + dl > location[r]) {
int nloc = location[l] + dl;
int dak = dr - (nloc - location[r]);
if (dak % 2 == 0) {
int tmp = location[r] - dak / 2;
auto it = mp[1].lower_bound(location[r]);
auto lmao = it;
if (it != mp[1].begin() && *(--it) == tmp) {
if (nloc > first && d0 == nloc - first) {
location[id] = nloc;
stype[id] = 2;
done = true;
}
}
}
}
if (!done && location[r] - dr < location[l]) {
int nloc = location[r] - dr;
int dak = (dl - (location[l] - nloc));
if (dak % 2 == 0) {
int tmp = location[l] + dak / 2;
auto it = mp[2].upper_bound(location[l]);
if (it != mp[2].end() && *it == tmp) {
if (nloc < first && d0 == 2 * second - first - nloc) {
location[id] = nloc;
stype[id] = 1;
done = true;
}
}
}
}
if (!done) {
assert(d[i + 1].first == d0);
swap(d[i], d[i + 1]);
i--;
}
mp[stype[id]].insert(location[id]);
if (stype[id] == 1) {
if (location[id] < location[l]) l = id;
}
if (stype[id] == 2) {
if (location[id] > location[r]) r = id;
}
}
}
Compilation message
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:81:22: warning: variable 'lmao' set but not used [-Wunused-but-set-variable]
81 | auto lmao = it;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
47 ms |
1104 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
48 ms |
1144 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |