제출 #341897

#제출 시각아이디문제언어결과실행 시간메모리
341897pit4h철로 (IOI14_rail)C++14
30 / 100
85 ms876 KiB
#include "rail.h" #include "bits/stdc++.h" #define st first #define nd second #define mp make_pair using namespace std; struct Station { int nr, pos, type; Station(int _nr, int _pos, int _type) { nr = _nr; pos = _pos; type = _type; } int distance(int Pos, int Type); }; vector<Station> stations; Station findPair(int pos, int type) { Station res(-1, -1, -1); for(Station st: stations) { if(type==0 && st.type==1 && pos < st.pos) { if(res.nr==-1 || abs(pos - st.pos) < abs(pos - res.pos)) { res = st; } } if(type==1 && st.type==0 && pos > st.pos) { if(res.nr==-1 || abs(pos - st.pos) < abs(pos - res.pos)) { res = st; } } } //assert(res.nr != -1); while(res.nr == -1){} return res; } int Station::distance(int Pos, int Type) { Station paired = findPair(pos, type); Station Paired = findPair(Pos, Type); int res = abs(pos - Pos); if((type==0 && pos > Pos) || (type==1 && pos < Pos)) res += 2*abs(pos - paired.pos); if((Type==0 && Pos > pos) || (Type==1 && Pos < pos)) res += 2*abs(Pos - Paired.pos); return res; } void findLocation(int N, int first, int location[], int stype[]) { location[0] = first; stype[0] = 1; stations.push_back( Station(0, first, 0) ); if(N==1) return; vector<pair<int, int>> vec(N-1); for(int i=1; i<N; ++i) { vec[i-1] = mp(getDistance(0, i), i); } sort(vec.begin(), vec.end()); stations.push_back( Station(vec[0].nd, location[0] + vec[0].st, 1) ); Station l = stations[0], r = stations[1]; vec.erase(vec.begin()); for(auto vi: vec) { int i = vi.nd; int dl = getDistance(l.nr, i), dr = getDistance(r.nr, i); vector<Station> cand = {Station(i, l.pos+dl, 1), Station(i, r.pos-dr, 0)}; int cnt_ok = 0; for(int j=0; j<2; ++j) { if(l.distance(cand[j].pos, cand[j].type) == dl && r.distance(cand[j].pos, cand[j].type) == dr) { cnt_ok++; stations.push_back(cand[j]); } } assert(cnt_ok == 1); if(stations.back().pos < l.pos) l = stations.back(); if(stations.back().pos > r.pos) r = stations.back(); } for(Station st: stations) { location[st.nr] = st.pos; stype[st.nr] = st.type+1; } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...