Submission #843033

#	Time	Username	Problem	Language	Result	Execution time	Memory
843033		coding_snorlax	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	13 ms	600 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
int Count = 0;
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==5) {
    Count++;
   	//waste_time
    set<int> sjdfijdifdj;
    if(Count > 30){
    
    for(int k = 0;k<1000000 * Count;k++){
      sjdfijdifdj.insert(k);
    }
    }
    }
    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);
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60