Submission #1212624

#TimeUsernameProblemLanguageResultExecution timeMemory
1212624AvianshLongest Trip (IOI23_longesttrip)C++20
15 / 100
3 ms416 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; pt1.push_back(0); for(int i = 1;i<n;i++){ int prev1 = pt1.back(); if(are_connected({prev1},{i})){ pt1.push_back(i); continue; } //not adjacent. if(pt2.size()){ int prev2 = pt2.back(); if(are_connected({prev2},{i})){ pt2.push_back(i); } else{ reverse(pt2.begin(),pt2.end()); pt1.insert(pt1.end(),pt2.begin(),pt2.end()); pt2.clear(); i--; continue; } } else{ pt2.push_back(i); } } if(pt2.size()==0){ return pt1; } if(!are_connected(pt1,pt2)){ if(pt1.size()>pt2.size()){ return pt1; } return pt2; } if(are_connected({pt1[0],pt1[pt1.size()-1]},{pt2[0],pt2[pt2.size()-1]})){ //ends connected //4 queries only 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; } 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)){ 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...