Submission #1243164

#TimeUsernameProblemLanguageResultExecution timeMemory
1243164nvujicaLongest Trip (IOI23_longesttrip)C++20
85 / 100
7 ms420 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; vector<int> longest_trip(int n, int d){ srand(time(0)); vector <int> v; for(int i = 0; i < n; i++) v.push_back(i); // int dosta = n * n; // for(int i = 0; i < dosta; i++){ // int p1 = rand() % n; // int p2 = rand() % n; // if(p1 != p2) swap(v[p1], v[p2]); // } vector <int> a, b; a.push_back(v[0]); for(int i = 1; i < n; i++){ //if(rand() % 2) swap(a, b); if(are_connected({a.back()}, {v[i]})) a.push_back(v[i]); else if(b.empty() || are_connected({b.back()}, {v[i]})) b.push_back(v[i]); else { while(!b.empty()){ a.push_back(b.back()); b.pop_back(); } b.push_back(v[i]); } } if(a.size() < b.size()) swap(a, b); if(a.size() == n) return a; if(are_connected({a.back()}, {b[0]})){ for(int i = 0; i < b.size(); i++){ a.push_back(b[i]); } return a; } if(are_connected({a.back()}, {b.back()})){ for(int i = b.size() - 1; i >= 0; i--){ a.push_back(b[i]); } return a; } if(are_connected({b.back()}, {a[0]})){ for(int i = 0; i < a.size(); i++){ b.push_back(a[i]); } return b; } if(!are_connected(a, b)) return a; int lo = 1, hi = a.size(); while(lo < hi){ int mid = (lo + hi) / 2; v.clear(); for(int i = 0; i < mid; i++){ v.push_back(a[i]); } if(are_connected(v, b)) hi = mid; else lo = mid + 1; } v.clear(); for(int i = hi; i < a.size(); i++) v.push_back(a[i]); for(int i = 0; i < hi; i++) v.push_back(a[i]); a = v; lo = 1, hi = b.size(); while(lo < hi){ int mid = (lo + hi) / 2; v.clear(); for(int i = 0; i < mid; i++){ v.push_back(b[i]); } if(are_connected({a.back()}, v)) hi = mid; else lo = mid + 1; } for(int i = hi - 1; i < b.size(); i++) a.push_back(b[i]); for(int i = 0; i < hi - 1; i++) a.push_back(b[i]); return a; }
#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...