Submission #288147

#	Time	Username	Problem	Language	Result	Execution time	Memory
288147		infinite_iq	Highway Tolls (IOI18_highway)	C++14	6 / 100	92 ms	2588 KiB

highway

#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define pb push_back
typedef long long ll ;
typedef vector < int > vi ;
typedef vector < ll  > vll ;
#include "highway.h"
ll n , m , len ; 
vi no ;
ll query ( vi ret ) {
        vi v ( m , 0 ) ;
        for ( auto u : ret ) v [u] = 1 ;
        return ask (v) ;
}
void find_pair ( int N , vi U, vi V , int A , int B ) {
        n = N , m = U .size () , len = query ( no ) / A ;
        ll l = 0 , r = n - 1 ; 
        while ( r - l > len ) {
                vi ret ;
                for ( ll i = mid ; i < r ; i ++ ) ret .pb ( i ) ;
                ll cost = query ( ret ) ;
                if ( cost == len * A ) {
                        r = mid ;
                }
                else if ( cost == len * B ) {
                        l = mid ;
                }
                else {
                        for ( ll i = 1 ; i <= mid - l ; i ++ ) {
                                if ( i * A + ( len - i ) * B == cost ) { 
                                        ll x = mid ; 
                                        l = x - i , r = x + len - i ;     
                                        goto out ;
                                }
                        }
                }
        }
        out :;
        answer ( (int)l , (int)r ) ;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31