Submission #1212679

#TimeUsernameProblemLanguageResultExecution timeMemory
1212679AvianshLongest Trip (IOI23_longesttrip)C++20
85 / 100
6 ms424 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; vector<int> longest_trip(int n, int D) { if(D==3){ vector<int>ans(n); iota(ans.begin(),ans.end(),0); return ans; } if(D==2){ set<int>lef; for(int i = 0;i<n;i++){ lef.insert(i); } vector<int>ans; ans.push_back(0); lef.erase(0); while(lef.size()>1){ if(are_connected({ans.back()},{*lef.begin()})){ ans.push_back(*lef.begin()); lef.erase(lef.begin()); } else{ ans.push_back(*(++lef.begin())); lef.erase(++lef.begin()); } } if(are_connected({*lef.begin()},{ans.back()})){ ans.push_back(*lef.begin()); return ans; } ans.insert(ans.begin(),*lef.begin()); return ans; } assert(D==1); vector<int>pt1,pt2; vector<int>order(n); iota(order.begin(),order.end(),0); random_shuffle(order.begin(),order.end()); pt1.push_back(order[0]); for(int i = 1;i<n;i++){ int prev1 = pt1.back(); if(are_connected({prev1},{order[i]})){ pt1.push_back(order[i]); continue; } //not adjacent. if(pt2.size()){ int prev2 = pt2.back(); if(are_connected({prev2},{order[i]})){ pt2.push_back(order[i]); } else{ reverse(pt2.begin(),pt2.end()); pt1.insert(pt1.end(),pt2.begin(),pt2.end()); pt2.clear(); i--; continue; } } else{ pt2.push_back(order[i]); } } if(pt2.size()==0){ return pt1; } if(!are_connected(pt1,pt2)){ if(pt1.size()>pt2.size()){ return pt1; } return pt2; } vector<int>t1; if(pt1.size()==1){ t1.push_back(pt1[0]); } else{ t1.push_back(pt1[0]); t1.push_back(pt1[pt1.size()-1]); } vector<int>t2; if(pt2.size()==1){ t2.push_back(pt2[0]); } else{ t2.push_back(pt2[0]); t2.push_back(pt2[pt2.size()-1]); } if(are_connected(t1,t2)){ //ends connected if(are_connected({pt1[0]},{pt2[0]})){ vector<int>ans; reverse(pt1.begin(),pt1.end()); for(int i : pt1){ ans.push_back(i); } for(int i : pt2){ ans.push_back(i); } return ans; } //fronts if(are_connected({pt1[0]},{pt2[pt2.size()-1]})){ vector<int>ans; for(int i : pt2){ ans.push_back(i); } for(int i : pt1){ ans.push_back(i); } return ans; } if(are_connected({pt1[pt1.size()-1]},{pt2[pt2.size()-1]})){ vector<int>ans; for(int i : pt1){ ans.push_back(i); } reverse(pt2.begin(),pt2.end()); for(int i : pt2){ ans.push_back(i); } return ans; } if(are_connected({pt1[pt1.size()-1]},{pt2[0]})){ vector<int>ans; for(int i : pt1){ ans.push_back(i); } for(int i : pt2){ ans.push_back(i); } return ans; } } //both cycles now. //must find joiner. int lo1 = 0; int hi1 = pt1.size()-1; while(lo1<hi1){ int mid = (lo1+hi1)/2; vector<int>quer; for(int i = 0;i<=mid;i++){ quer.push_back(pt1[i]); } if(are_connected(quer,pt2)){ hi1=mid; } else{ lo1=mid+1; } } int lo2 = 0; int hi2 = pt2.size()-1; while(lo2<hi2){ int mid = (lo2+hi2)/2; vector<int>quer; for(int i = 0;i<=mid;i++){ quer.push_back(pt2[i]); } if(are_connected(quer,{pt1[lo1]})){ hi2=mid; } else{ lo2=mid+1; } } vector<int>ans; for(int i = 1;i<=pt1.size();i++){ ans.push_back(pt1[(i+lo1)%(pt1.size())]); } for(int i = pt2.size();i>0;i--){ ans.push_back(pt2[(i+lo2)%(pt2.size())]); } return ans; }
#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...