| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 842993 | coding_snorlax | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
set<int> un_process;
vector<int> B_complex_graph(vector<int> A,vector<int> B){
set<int> test;
vector<int> test_1;
for(int i:A){
if(test.find(i)!=test.end()) return test_1;
test.insert(i);
}
for(int i:B){
if(test.find(i)!=test.end()) return test_1;
test.insert(i);
}
// B is a complex_graph set
vector<int> tmp={0},tmp1={0};
tmp[0] = A[0];
if(!are_connected(tmp,B)){
// now A[0],A.back() connected
// only need to find one edge between A and B or return no such edge
int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
while(L!=R){
vector<int> query;
M = (L+R)/2;
for(int i=L;i<=M;i++){
query.push_back(B[i]);
}
if(!are_connected(A,query)) L = M+1;
else R = M;
}
int l = 0;int r = (int) A.size()-1;int m = (L+R)/2;
while(l!=r){
vector<int> query;
m = (l+r)/2;
for(int i=l;i<=m;i++){
query.push_back(A[i]);
}
tmp[0]=B[L];
if(!are_connected(query,tmp)) l = m+1;
else r = m;
}
tmp1[0]=A[l];
if(are_connected(tmp1,tmp)){
vector<int> answer;
for(int i=0;i<(int)A.size();i++) answer.push_back(A[(i+l+1)%((int)A.size())]);
answer.push_back(B[L]);
for(int i=0;i<(int)B.size()-1;i++) answer.push_back(B[(i+L+1)%((int)B.size())]);
return answer;
}
else{
return A;
}
}
else{
int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
while(L!=R){
vector<int> query;
M = (L+R)/2;
for(int i=L;i<=M;i++){
query.push_back(B[i]);
}
if(!are_connected(tmp,query)) L = M+1;
else R = M;
}
vector<int> answer;
for(int i=(int)A.size()-1;i>=0;i--) answer.push_back(A[i]);
answer.push_back(B[R]);
//cout << "B_size" << (int)B.size() << "\n";
for(int i=0;i<(int)B.size()-1;i++) answer.push_back(B[(i+R+1)%((int)B.size())]);
return answer;
}
}
vector<int> Process(vector<int> C,vector<int> D){
if((int)D.size()==0) {return C;}
vector<int> A,B;
if((int)C.size()<(int)D.size()){A=D;B=C;}
else{A=C;B=D;}
vector<int> tmp = {1};
tmp[0] = A.back();
if(!are_connected(tmp,B)){
return B_complex_graph(A,B);
}
else{
int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
while(L!=R){
vector<int> query;
M = (L+R)/2;
cout << M << " \n";
for(int i=L;i<=M;i++){
query.push_back(B[i]);
}
if(!are_connected(tmp,query)) L = M+1;
else R = M;
}
vector<int> new_B;
if(L > (int)B.size()/2){
for(int i=L;i>=0;i--){
A.push_back(B[i]);
}
for(int i=L+1;i<(int)B.size();i++){
new_B.push_back(B[i]);
}
}
else{
for(int i=L;i<(int)B.size();i++){
A.push_back(B[i]);
}
for(int i=L-1;i>=0;i--){
new_B.push_back(B[i]);
}
}
return Process(A,new_B);
}
}
vector<int> longest_trip(int N, int D)
{
if(N>50) std::this_thread::sleep_for(std::chrono::seconds(0.05));
un_process.clear();
for(int i=2;i<N;i++){
un_process.insert(i);
}
vector<int> a={0};
vector<int> b={1};
while((int)un_process.size()>=1){
vector<int> ask1 = {a.back()};
vector<int> ask2 = {b.back(),*un_process.begin()};
if(are_connected(ask1,ask2)){
vector<int> ask3 = {a.back()};
vector<int> ask4 = {*un_process.begin()};
if(are_connected(ask3,ask4)) a.push_back(*un_process.begin());
else{
for(int i = (int)b.size()-1;i>=0;i--) a.push_back(b[i]);
b.clear();
b.push_back(*un_process.begin());
}
}
else{
b.push_back(*un_process.begin());
}
un_process.erase(un_process.begin());
}
return Process(a,b);
}