Submission #288121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
288121	2020-09-01T08:54:01 Z	infinite_iq	Highway Tolls (IOI18_highway)	C++14	0 / 100	172 ms	2592 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	256 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	384 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	640 KB	Output is correct
2	Correct	40 ms	872 KB	Output is correct
3	Correct	29 ms	1016 KB	Output is correct
4	Correct	87 ms	2584 KB	Output is correct
5	Correct	89 ms	2456 KB	Output is correct
6	Correct	128 ms	2584 KB	Output is correct
7	Correct	96 ms	2584 KB	Output is correct
8	Correct	134 ms	2584 KB	Output is correct
9	Incorrect	172 ms	2592 KB	Output is incorrect: more than 100 calls to ask.