Submission #1238746

#TimeUsernameProblemLanguageResultExecution timeMemory
1238746CyberCowLongest Trip (IOI23_longesttrip)C++20
5 / 100
5 ms404 KiB
#include "longesttrip.h" #include <vector> #include <deque> #include <algorithm> using namespace std; vector<int> longest_trip(int N, int D) { vector<int> ans; vector<int> a = { 0 }, b = { 1 }; for (int i = 2; i < N; i++) { if (are_connected({ a.back() }, { i })) { a.push_back(i); } else if (are_connected({ b.back() }, { i })) { b.push_back(i); } else { for (int j = b.size() - 1; j >= 0; j--) { a.push_back(b[j]); } b.clear(); b.push_back(i); } } if (a.size() < b.size())swap(a, b); if (are_connected(a, b)) { if (are_connected({ a[0] }, { a.back() })) { if (b.size() == 1) { int l = 0, r = a.size() - 1, ass; while (l <= r) { vector<int> harc; int m = (l + r) / 2; for (int i = l; i <= m; i++) { harc.push_back(a[i]); } if (are_connected(harc, b)) { ass = m; r = m - 1; } else { l = m + 1; } } ans.push_back(b[0]); for (int i = ass; i < a.size(); i++) { ans.push_back(a[i]); } for (int i = 0; i < ass; i++) { ans.push_back(a[i]); } return ans; } if (!are_connected({ b[0] }, { b.back() })) { if (are_connected({ a.back() }, { b.back() })) { while (!b.empty()) { a.push_back(b.back()); b.pop_back(); } return a; } reverse(b.begin(), b.end()); while (!b.empty()) { a.push_back(b.back()); b.pop_back(); } return a; } int l = 0, r = a.size() - 1, ass; while (l <= r) { vector<int> harc; int m = (l + r) / 2; for (int i = l; i <= m; i++) { harc.push_back(a[i]); } if (are_connected(harc, b)) { ass = m; r = m - 1; } else { l = m + 1; } } l = 0; r = b.size() - 1; int ass1; while (l <= r) { vector<int> harc; int m = (l + r) / 2; for (int i = l; i <= m; i++) { harc.push_back(b[i]); } if (are_connected(harc, a)) { ass1 = m; r = m - 1; } else { l = m + 1; } } for (int i = ass + 1; i < a.size(); i++) { ans.push_back(a[i]); } for (int i = 0; i <= ass; i++) { ans.push_back(a[i]); } for (int i = ass1; i < b.size(); i++) { ans.push_back(b[i]); } for (int i = 0; i < ass1; i++) { ans.push_back(b[i]); } return ans; } else { if (are_connected({ a.back() }, { b.back() })) { while (!b.empty()) { a.push_back(b.back()); b.pop_back(); } return a; } reverse(a.begin(), a.end()); while (!b.empty()) { a.push_back(b.back()); b.pop_back(); } return a; } } else return a; throw; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...