Submission #893204

#	Time	Username	Problem	Language	Result	Execution time	Memory
893204		vjudge1	커다란 상품 (IOI17_prize)	C++17	90 / 100	44 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(2);
    sumv = 0;
    for(int i = 0; i < 200; ++i) {
        int p = uniform_int_distribution<int>(0, n - 1)(rng);
        //cout << p << "\n";
        vi a = ask(p);
        sumv = max(sumv, a[0] + a[1]);
    }
    int p = -1, ulta0 = 0;
    int re = 0;
    while(p < n) { /// p e ultima pozitie verificata, stim ca e buna
        for(int step = 20; step >= 0; --step) {
            if(p + (1 << step) < n) {
                vi a = ask(p + (1 << step));
                if(a[0] + a[1] > sumv)
                    sumv = a[0] + a[1];
                //assert(a[0] + a[1] <= sumv);
                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);
        if(a[0] + a[1] > sumv)
            sumv = a[0] + a[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:21:9: warning: unused variable 're' [-Wunused-variable]
   21 |     int re = 0;
      |         ^~

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