제출 #1212670

#제출 시각아이디문제언어결과실행 시간메모리
1212670Aviansh가장 긴 여행 (IOI23_longesttrip)C++20
15 / 100
5 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; } 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; } } vector<int> new_pt1; for (int i = 0; i < pt1.size(); i++) { new_pt1.push_back(pt1[(lo1 + i) % pt1.size()]); } int left = 0, right = pt2.size()-1; while (left < right) { int mid = (left+right)/2; vector<int> query_pt2; for (int i = 0; i <= mid; i++) { query_pt2.push_back(pt2[i]); } if (are_connected({new_pt1[0]}, query_pt2)) { right = mid; } else { left = mid+1; } } int x_index = left; vector<int> new_pt2; for (int i = 0; i < pt2.size(); i++) { new_pt2.push_back(pt2[(x_index + i) % pt2.size()]); } new_pt1.insert(new_pt1.end(), new_pt2.begin(), new_pt2.end()); return new_pt1; }
#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...