Submission #883562

#TimeUsernameProblemLanguageResultExecution timeMemory
883562ono_de206Rail (IOI14_rail)C++14
8 / 100
88 ms98652 KiB
#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)); int cnt = 0; auto get = [&](int x, int y) -> int { if(x > y) swap(x, y); if(dis[x][y] != -1) return dis[x][y]; cnt++; if(cnt > 2 * n) exit(1); 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(get(ls, x) - get(0, x) + get(0, tmp) == pos[ls] - pos[tmp]) { res.pb(x); } else if(get(x, ls) > get(0, ls) || 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)); tp[x] = 1; pos[x] = pos[ls] - get(ls, x); } } if(res.size()) { ls = res[0], ll = pos[tmp]; res.erase(res.begin()); tp[ls] = 1; pos[ls] = pos[0] - get(0, ls) + 2 * get(0, tmp); for(int x : res) { if(get(x, ls) > get(0, ls) - 2 * get(0, tmp) || 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); // cout << tp[i] << ' ' << pos[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...