Submission #713259

#	Time	Username	Problem	Language	Result	Execution time	Memory
713259		tht2005	The Big Prize (IOI17_prize)	C++17	90 / 100	81 ms	336 KiB

prize

#include "prize.h"

int find_best(int n) {
    int big = 0;
    std::vector<int> q_big(2, -1);
    for(int i = 0; i < n && i < 500; ++i) {
        std::vector<int> q = ask(i);
        if(q[0] == 0 && q[1] == 0) {
            return i;
        }
        if(q_big[0] + q_big[1] <= q[0] + q[1]) {
            big = i;
            q_big = q;
        }
    }
    while(big + 1 < n) {
        int l = big + 1, r = n - 1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            std::vector<int> q = ask(mid);
            if(q[0] + q[1] < q_big[0] + q_big[1] || q[1] < q_big[1]) {
                r = mid - 1;
            }
            else {
                big = mid;
                l = mid + 1;
            }
        }
        for(int i = big + 1; i < n; ++i) {
            std::vector<int> q = ask(i);
            if(q[0] == 0 && q[1] == 0) {
                return i;
            }
            if(q[0] + q[1] == q_big[0] + q_big[1]) {
                big = i;
                q_big = q;
                break;
            }
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:5:33: warning: control reaches end of non-void function [-Wreturn-type]
    5 |     std::vector<int> q_big(2, -1);
      |                                 ^

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