Submission #288130

#	Time	Username	Problem	Language	Result	Execution time	Memory
288130		infinite_iq	Highway Tolls (IOI18_highway)	C++14	0 / 100	202 ms	2632 KiB

highway

#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define pb push_back
typedef vector < int > vi ;
#include "highway.h"
int n , m , len ;
vi no ;
int 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 ;
        int l = 0 , r = n - 1 ;
//      cout << len << endl ; 
        while ( r - l > len ) {
        //      cout << l << " " << r << " " << mid << " " ;
                vi ret ;
                for ( int i = mid ; i < r ; i ++ ) ret .pb ( i ) ;
                int cost = query ( ret ) ;
        //      cout << cost << endl ; 
                if ( cost == len * A ) {
                        r = mid ;
                }
                else if ( cost == len * B ) {
                        l = mid ;
                }
                else {
                        for ( int i = 1 ; i <= mid - l ; i ++ ) {
                                if ( i * A + ( len - i ) * B == cost ) { 
                                        l = mid - i , r = mid + len - i ;
                                }
                        }
                }
        }
//      cout << l << " " << r << endl ; 
        answer ( l , r ) ;
}

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