Submission #703437

#	Time	Username	Problem	Language	Result	Execution time	Memory
703437		SamNguyen	The Big Prize (IOI17_prize)	C++14	0 / 100	85 ms	5408 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
    if (x < y) { x = y; return true; }
    return false;
}

namespace SUB1 {
    int find_best(int n) {
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = (l + r) >> 1;
            auto cnt = ask(m);

            if (cnt[0] == cnt[1])
                return m;

            if (cnt[0] < cnt[1])
                l = m + 1;
            else
                r = m - 1;
        }

        return -1;
    }
}

namespace SUB2A {
    vector<int> inds;
    int MAX_S;

    vector<vector<int>> cnt;

    vector<int>& count(int i) {
        if (cnt[i].empty())
            cnt[i] = ask(i);
        return cnt[i];
    }

    int count_both(int i) {
        auto &a = count(i);
        return a[0] + a[1];
    }

    void extract(int l, int r) {
//        cout << "extract " << l << " " << r << endl;

        if (l > r)
            return;

        if (count_both(l) < MAX_S) {
            inds.push_back(l);
            extract(l + 1, r);
            return;
        }

        if (count_both(r) < MAX_S) {
            inds.push_back(r);
            extract(l, r - 1);
            return;
        }

        if (l == r)
            return;

        int m = (l + r) >> 1;
        if (count_both(m) < MAX_S) {
            inds.push_back(m);
            extract(l, m - 1);
            extract(m + 1, r);
        }
        else {
            extract(l, m - 1);
            extract(m + 1, r);
        }
    }

    int find_best(int n) {
        cnt.assign(n, vector<int>());

        MAX_S = 0;
        for (int i = 0; i < n and i < 1000; i++) {
            int s = count_both(i);
            if (s == 0)
                return i;
            maximise(MAX_S, s);
        }

//        cout << "MAX_S = " << MAX_S << endl;

        extract(0, n - 1);

        for (int i : inds)
            if (count_both(i) == 0)
                return i;

        return -1;
    }
}

int find_best(int n) {
    return SUB2A::find_best(n);
}

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