Submission #1206477

#TimeUsernameProblemLanguageResultExecution timeMemory
1206477hyakup가장 긴 여행 (IOI23_longesttrip)C++20
5 / 100
5 ms416 KiB
#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); }
#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...