제출 #883549

#제출 시각아이디문제언어결과실행 시간메모리
883549ono_de206철로 (IOI14_rail)C++14
30 / 100
91 ms98640 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)); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...