Submission #1282939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282939		wenbang	The Big Prize (IOI17_prize)	C++20	97.78 / 100	18 ms	416 KiB

prize

#include "prize.h"
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

#ifdef LOCAL
#include "../print.h"
#else
template <typename... Args> inline void print(const Args&... args) {}
inline void                             newline() {}
#endif

using ll  = long long;
using pii = std::pair<int, int>;
#define endl                       '\n'
#define FOR1(n)                    for (int _ = 0; _ < n; _++)
#define FOR2(i, n)                 for (int i = 0; i < n; i++)
#define FOR3(i, a, b)              for (int i = a; i < b; i++)
#define overload3(a, b, c, d, ...) d
#define FOR(...)                   overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)

using namespace std;

int search(int l, int r, pii left, pii right) {
    if (l > r) {
        return -1;
    }
    int         m    = (l + r) / 2;
    vector<int> c    = ask(m);
    pii         curr = {c [0], c [1]};
    if (c [0] == 0 && c [1] == 0) {
        return m;
    }
    if (l == r) {
        return -1;
    }
    int ret = -1;
    if (c [1] > 0 && curr != right) {
        ret = search(m + 1, r, curr, right);
    }
    if (ret == -1 && c [0] > 0 && curr != left) {
        ret = search(l, m - 1, left, curr);
    }
    return ret;
}

int find_best(int n) {
    return search(0, n - 1, {-1, -1}, {-1, -1});
}

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