Submission #893202

#	Time	Username	Problem	Language	Result	Execution time	Memory
893202		vjudge1	커다란 상품 (IOI17_prize)	C++17	0 / 100	0 ms	436 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 < 100; ++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));
                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);
        assert(a[0] + a[1] <= sumv);
        //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: 0 / 20
• Subtask 2: 0 / 80