제출 #1026096

#제출 시각아이디문제언어결과실행 시간메모리
1026096socpite철로 (IOI14_rail)C++17
0 / 100
44 ms860 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[]) { map<int, int> mp; stype[0] = 1; location[0] = first; mp[location[0]] = 0; vector<pair<int, int>> vec; int fd = -1; for(int i = 1; i < N; i++){ distC[i] = getDistance(0, i); // cout << distC[i] << endl; if(fd == -1 || distC[i] < distC[fd])fd = i; } cout << fd << endl; stype[fd] = 2; location[fd] = first + distC[fd]; mp[location[fd]] = 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 lpos = *prev(st.upper_bound(fakepos)); int checkdist = fakepos + location[fd] - lpos*2; if(checkdist == v.first && st.find(fakepos) == st.end() && getDistance(mp[lpos], v.second) == fakepos - lpos){ 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; } mp[location[v.second]] = v.second; } 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 rpos = *st.lower_bound(fakepos); int checkdist = rpos*2 - first - fakepos; if(checkdist == v.first && st.find(fakepos) == st.end() && getDistance(mp[rpos], v.second) == rpos - fakepos){ 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; } mp[location[v.second]] = v.second; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...