Submission #599149

#	Time	Username	Problem	Language	Result	Execution time	Memory
599149		pakhomovee	The Big Prize (IOI17_prize)	C++17	20 / 100	93 ms	336 KiB

prize

#include "prize.h"
#include <vector>
#include <map>
#include <cassert>

int find_best(int n) {
    int pr = 0;
    std::map<int, int> d;
    int Q = 1;
    std::vector<int> q = ask(0);
    int lt = q[0];
    int rt = q[1];
    int sm = lt + rt;
    if (sm == 0) {
        return 0;
    }
    while (pr != n) {
        int l = pr, r = n;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            int have = 0;
            std::vector<int> q = ask(m);
            ++Q;
            int lt = q[0];
            int rt = q[1];
            for (auto [x, y] : d) {
                if (lt + rt > x) {
                    have += y;
                }
            }
            if (sm != lt + rt || lt - have) {
                r = m;
            } else {
                l = m;
            }
        }
        std::vector<int> arr = ask(l);
        ++Q;
        if (arr[0] == arr[1] && arr[0] == 0) {
            return l;
        }
        ++d[arr[0] + arr[1]];
        pr = l + 1;
    }
    assert(Q < 5000);
    return -1;
}

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