Submission #893131

#	Time	Username	Problem	Language	Result	Execution time	Memory
893131		vjudge1	커다란 상품 (IOI17_prize)	C++17	20 / 100	47 ms	600 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 < 20; ++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) {
        if(p != -1) {
            vi a = ask(p + 1);
            if(a[0] + a[1] == sumv) {
                ulta0 = a[0];
            } else {
                if(a[0] + a[1] == 0) return p + 1;
                ++p;
                continue;
            }
        }
        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);
            }
        }
        /// p + 1 e special
        vi a = ask(p + 1);
        if(a[0] + a[1] == 0) {
            return p + 1; 
        }
        ++p;
    }
    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