제출 #893203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893203		vjudge1	커다란 상품 (IOI17_prize)	C++17	20 / 100	57 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(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;
}

컴파일 시 표준 에러 (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: 0 / 80