Submission #1145473

#TimeUsernameProblemLanguageResultExecution timeMemory
1145473AlgorithmWarriorLongest Trip (IOI23_longesttrip)C++20
85 / 100
5 ms420 KiB
#include "longesttrip.h" #include <cassert> #include <cstdio> #include <string> #include <vector> #include <deque> #include <bits/stdc++.h> using namespace std; vector<int>prefix(vector<int>v,int ind){ vector<int>pref; int i; for(i=0;i<=ind;++i) pref.push_back(v[i]); return pref; } vector<int>ocol(vector<int>v,int val){ int i; int poz=0; for(i=0;i<(int)v.size();++i) if(v[i]==val) poz=i; vector<int>ans; for(i=poz-1;i>=0;--i) ans.push_back(v[i]); for(i=v.size()-1;i>poz;--i) ans.push_back(v[i]); return ans; } std::vector<int> longest_trip(int N, int D){ if(D==3){ int i; vector<int>path; for(i=0;i<N;++i) path.push_back(i); return path; } else if(D==2){ int i; deque<int>path; int vec0; if(are_connected({0},{1})) vec0=1; else vec0=2; path.push_back(0); path.push_back(vec0); for(i=1;i<N;++i) if(i!=vec0){ if(are_connected({path.front()},{i})) path.push_front(i); else path.push_back(i); } vector<int>ans; for(auto el : path) ans.push_back(el); return ans; } else{ vector<int>unu,doi; int i; vector<int>perm; for(i=0;i<N;++i) perm.push_back(i); srand(time(0)); for(i=1;i<N;++i){ int sch=rand()%(i+1); swap(perm[i],perm[sch]); } unu.push_back(perm[0]); int ifor; for(ifor=1;ifor<N;++ifor){ i=perm[ifor]; if(doi.empty()){ if(are_connected({unu.back()},{i})) unu.push_back(i); else doi.push_back(i); } else{ if(rand()%2==0) swap(unu,doi); if(!are_connected({unu.back()},{i})) doi.push_back(i); else{ if(!are_connected({doi.back()},{i})) unu.push_back(i); else{ unu.push_back(i); reverse(doi.begin(),doi.end()); for(auto el : doi) unu.push_back(el); doi.clear(); } } } } if(doi.empty()) return unu; if(!are_connected(unu,doi)){ if(unu.size()<doi.size()) swap(unu,doi); return unu; } if(are_connected({unu.front()},{doi.front()})){ reverse(unu.begin(),unu.end()); for(auto el : doi) unu.push_back(el); return unu; } if(are_connected({unu.front()},{doi.back()})){ reverse(unu.begin(),unu.end()); reverse(doi.begin(),doi.end()); for(auto el : doi) unu.push_back(el); return unu; } if(are_connected({unu.back()},{doi.front()})){ for(auto el : doi) unu.push_back(el); return unu; } /// (] int st=-1,dr=unu.size()-1; while(dr-st>1){ int mij=(st+dr)/2; if(are_connected(prefix(unu,mij),doi)) dr=mij; else st=mij; } vector<int>unu_nod; unu_nod.push_back(unu[dr]); st=-1,dr=doi.size()-1; while(dr-st>1){ int mij=(st+dr)/2; if(are_connected(prefix(doi,mij),unu_nod)) dr=mij; else st=mij; } vector<int>rasp; vector<int>part; part=ocol(unu,unu_nod[0]); for(auto el : part) rasp.push_back(el); rasp.push_back(unu_nod[0]); rasp.push_back(doi[dr]); part=ocol(doi,doi[dr]); for(auto el : part) rasp.push_back(el); return rasp; } }
#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...