Submission #1026092

#TimeUsernameProblemLanguageResultExecution timeMemory
1026092socpiteRail (IOI14_rail)C++17
30 / 100
45 ms780 KiB
#include "rail.h" #include<bits/stdc++.h> using namespace std; const int maxn = 5e3 + 5; int distC[maxn], distD[maxn]; void findLocation(int N, int first, int location[], int stype[]) { stype[0] = 1; location[0] = first; vector<pair<int, int>> vec; int fd = -1; for(int i = 1; i < N; i++){ distC[i] = getDistance(0, i); if(fd == -1 || distC[i] < distC[fd])fd = i; } stype[fd] = 2; location[fd] = first + distC[fd]; for(int i = 1; i < N; i++){ if(i == fd)continue; distD[i] = getDistance(fd, i); if(distD[i] < distC[i])vec.push_back({distD[i], i}); } sort(vec.begin(), vec.end()); set<int> st; st.insert(first); int mxid = 0; for(auto v: vec){ int d = getDistance(v.second, mxid); int fakepos = *st.begin() + d; int checkdist = fakepos + location[fd] - *prev(st.upper_bound(fakepos))*2; if(checkdist == v.first && st.find(fakepos) == st.end()){ location[v.second] = fakepos; stype[v.second] = 2; } else { mxid = v.second; location[v.second] = location[fd] - v.first; st.insert(location[v.second]); stype[v.second] = 1; } } st.clear(); vec.clear(); for(int i = 1; i < N; i++){ if(i == fd)continue; if(distC[i] < distD[i])vec.push_back({distC[i], i}); } sort(vec.begin(), vec.end()); st.insert(location[fd]); mxid = fd; for(auto v: vec){ int d = getDistance(v.second, mxid); int fakepos = *st.rbegin() - d; int checkdist = *st.lower_bound(fakepos)*2 - first - fakepos; if(checkdist == v.first && st.find(fakepos) == st.end()){ location[v.second] = fakepos; stype[v.second] = 1; } else { mxid = v.second; location[v.second] = first + v.first; st.insert(location[v.second]); stype[v.second] = 2; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...