# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
883547 |
2023-12-05T11:56:48 Z |
ono_de206 |
Rail (IOI14_rail) |
C++14 |
|
179 ms |
199828 KB |
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
//#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
void findLocation(int n, int first, int pos[], int tp[]) {
pos[0] = first;
tp[0] = 1;
if(n == 1) return;
vector<vector<int>> dis(n, vector<int>(n, -1));
auto get = [&](int x, int y) -> int {
if(x > y) swap(x, y);
if(dis[x][y] != -1) return dis[x][y];
return dis[x][y] = getDistance(x, y);
};
vector<int> id(n - 1);
iota(all(id), 1);
sort(all(id), [&](int x, int y) {
return get(0, x) < get(0, y);
});
vector<int> res;
int ls = id[0], tmp = id[0], ll = pos[0];
id.erase(id.begin());
tp[ls] = 2;
pos[ls] = pos[0] + get(0, ls);
for(int x : id) {
if(pos[ls] - ll + pos[0] + get(0, x) - ll == get(x, ls)) {
tp[x] = 2;
pos[x] = pos[0] + get(0, x);
ls = x;
} else {
ll = max(ll, pos[ls] - get(ls, x));
if(pos[ls] - get(ls, x) >= pos[0]) {
tp[x] = 1;
pos[x] = pos[ls] - get(ls, x);
} else {
res.pb(x);
}
}
}
if(res.size()) {
ls = res[0], ll = pos[0] + get(0, tmp);
res.erase(res.begin());
tp[ls] = 1;
pos[ls] = pos[0] - get(0, ls) + 2 * get(0, tmp);
for(int x : res) {
if(ll - (pos[0] - get(0, x) + 2 * get(0, tmp)) + ll - pos[ls] == get(ls, x)) {
tp[x] = 1;
pos[x] = pos[0] - get(0, x) + 2 * get(0, tmp);
ls = x;
} else {
ll = min(ll, pos[ls] + get(ls, x));
tp[x] = 2;
pos[x] = pos[ls] + get(ls, x);
}
}
}
for(int i = 0; i < n; i++) {
assert(pos[i] >= 0 && pos[i] < 1000000);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 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 |
1 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 |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
520 KB |
Output is correct |
6 |
Correct |
1 ms |
520 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
179 ms |
199828 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
175 ms |
199768 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |