Submission #893146

#	Time	Username	Problem	Language	Result	Execution time	Memory
893146		vjudge1	The Big Prize (IOI17_prize)	C++17	20 / 100	50 ms	852 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int sumv;

int find_best(int n) {
    mt19937 rng(1);
    for(int i = 0; i < 30; ++i) {
        int p = uniform_int_distribution<int>(0, n - 1)(rng);
        vi a = ask(p);
        sumv = max(sumv, a[0] + a[1]);
    }
    int p = -1, ulta0 = 0;
    int re = 0;
    while(p < n) {
        for(int step = 20; step >= 0; --step) {
            if(p + (1 << step) < n) {
                vi a = ask(p + (1 << step));
                if(a[0] + a[1] == sumv && a[0] == ulta0)
                    p += (1 << step);
                if(a[0] + a[1] == 0) return p + (1 << step);
            }
        }
        if(p + 1 >= n) break;
        /// p + 1 e special
        vi a = ask(p + 1);
        assert((a[0] + a[1]) != sumv);
        if(a[0] + a[1] == 0) {
            return p + 1; 
        }
        ++p;
        ++ulta0;
    }
    return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:19:9: warning: unused variable 're' [-Wunused-variable]
   19 |     int re = 0;
      |         ^~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80