Submission #842993

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
842993	2023-09-03T14:21:14 Z	coding_snorlax	Longest Trip (IOI23_longesttrip)	C++17	Compilation error	0 ms	0 KB

longesttrip

#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);
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:118:67: error: no matching function for call to 'std::chrono::duration<long int>::duration(double)'
  118 |     if(N>50) std::this_thread::sleep_for(std::chrono::seconds(0.05));
      |                                                                   ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:101,
                 from longesttrip.cpp:2:
/usr/include/c++/10/chrono:429:14: note: candidate: 'template<class _Rep2, class _Period2, class> constexpr std::chrono::duration<_Rep, _Period>::duration(const std::chrono::duration<_Rep, _Period>&) [with _Rep2 = _Rep2; _Period2 = _Period2; <template-parameter-2-3> = <template-parameter-1-3>; _Rep = long int; _Period = std::ratio<1>]'
  429 |    constexpr duration(const duration<_Rep2, _Period2>& __d)
      |              ^~~~~~~~
/usr/include/c++/10/chrono:429:14: note:   template argument deduction/substitution failed:
longesttrip.cpp:118:67: note:   mismatched types 'const std::chrono::duration<_Rep1, _Period1>' and 'double'
  118 |     if(N>50) std::this_thread::sleep_for(std::chrono::seconds(0.05));
      |                                                                   ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:101,
                 from longesttrip.cpp:2:
/usr/include/c++/10/chrono:422:23: note: candidate: 'template<class _Rep2, class> constexpr std::chrono::duration<_Rep, _Period>::duration(const _Rep2&) [with _Rep2 = _Rep2; <template-parameter-2-2> = <template-parameter-1-2>; _Rep = long int; _Period = std::ratio<1>]'
  422 |    constexpr explicit duration(const _Rep2& __rep)
      |                       ^~~~~~~~
/usr/include/c++/10/chrono:422:23: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/stl_pair.h:59,
                 from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from longesttrip.h:1,
                 from longesttrip.cpp:1:
/usr/include/c++/10/type_traits: In substitution of 'template<bool _Cond, class _Tp> using __enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = void]':
/usr/include/c++/10/type_traits:2195:11:   required by substitution of 'template<class ... _Cond> using _Require = std::__enable_if_t<std::__and_< <template-parameter-1-1> >::value> [with _Cond = {std::is_convertible<const double&, long int>, std::__or_<std::chrono::treat_as_floating_point<long int>, std::__not_<std::chrono::treat_as_floating_point<double> > >}]'
/usr/include/c++/10/chrono:419:27:   required from here
/usr/include/c++/10/type_traits:2192:11: error: no type named 'type' in 'struct std::enable_if<false, void>'
 2192 |     using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
      |           ^~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:101,
                 from longesttrip.cpp:2:
/usr/include/c++/10/chrono:415:2: note: candidate: 'constexpr std::chrono::duration<_Rep, _Period>::duration(const std::chrono::duration<_Rep, _Period>&) [with _Rep = long int; _Period = std::ratio<1>]'
  415 |  duration(const duration&) = default;
      |  ^~~~~~~~
/usr/include/c++/10/chrono:415:11: note:   no known conversion for argument 1 from 'double' to 'const std::chrono::duration<long int>&'
  415 |  duration(const duration&) = default;
      |           ^~~~~~~~~~~~~~~
/usr/include/c++/10/chrono:413:12: note: candidate: 'std::chrono::duration<_Rep, _Period>::duration() [with _Rep = long int; _Period = std::ratio<1>]'
  413 |  constexpr duration() = default;
      |            ^~~~~~~~
/usr/include/c++/10/chrono:413:12: note:   candidate expects 0 arguments, 1 provided