Submission #1206477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206477		hyakup	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	5 ms	416 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;

bool check( int x, int y ){
  vi a = {x}, b = {y};
  return are_connected( a, b );
}

bool query( vi &a, vi &b, int la, int ra ){
  vi aux( a.begin() + la, a.begin() + ra );
  return are_connected( aux, b );
}

vi solve3( int n ){
  vi v(n);
  iota( v.begin(), v.end(), 0 );
  return v;
}

vi solve2( int n ){
  deque<int> dq;
  dq.push_back(0);
  for( int i = 1; i < n; i++ ){
    if( check( i, dq.back() ) ) dq.push_back(i);
    else dq.push_front(i);
  }

  vi resp( dq.begin(), dq.end() );
  return resp;
}

void merge( vi &a, vi &b ){
  while( !b.empty() ){
    a.push_back(b.back());
    b.pop_back();
  }
}

int bs( vector<int> &a, vector<int> &b ){
  int l = 0, r = a.size();
  while( l + 1 < r ){
    int mid = ( l + r )/2;
    if( !query( a, b, l, mid ) ) l = mid;
    else r = mid;
  }
  return l;
}

vi solve1( int n ){
  vi a( 1, 0 ), b( 1, 1 );
  for( int i = 2; i < n; i++ ){
    if( check( a.back(), i ) ){ a.push_back(i); continue; }
    if( check( b.back(), i ) ){ b.push_back(i); continue; }

    merge( a, b );
    b.push_back(i);
  }

  if( !query( a, b, 0, a.size() ) ) return a;
  if( check( a.back(), b.back() ) ){
    merge( a, b );
    return a;
  }
  reverse( a.begin(), a.end() );
  if( check( a.back(), b.back() ) ){
    merge( a, b );
    return a;
  }
  reverse( b.begin(), b.end() );
  if( check( a.back(), b.back() ) ){
    merge( a, b );
    return a;
  }
  reverse( a.begin(), a.end() );
  if( check( a.back(), b.back() ) ){
    merge( a, b );
    return a;
  }


  int id1 = bs( a, b );
  int id2 = bs( b, a );

  vi resp;
  for( int i = (id1 + 1)%a.size(); resp.size() < a.size(); i = (i + 1)%a.size() )
    resp.push_back(a[i]);
  for( int i = id2; (int)resp.size() < n; i = (i + 1)%b.size() )
    resp.push_back(b[i]);

  return resp;
}

vi longest_trip( int n, int d ){
    if( d == 3 ) return solve3(n);
    if( d == 2 ) return solve2(n);
    return solve1(n);
}

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