Submission #703507

#	Time	Username	Problem	Language	Result	Execution time	Memory
703507		SamNguyen	The Big Prize (IOI17_prize)	C++14	90 / 100	80 ms	5224 KiB

prize

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

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

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

template <class F>
int FIND_SMALLEST(int l, int r, F f) {
    int res = r + 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (f(m)) res = m, r = m - 1;
        else l = m + 1;
    }
    return res;
}

template <class F>
int FIND_LARGEST(int l, int r, F f) {
    int res = l - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (f(m)) res = m, l = m + 1;
        else r = m - 1;
    }
    return res;
}

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 n, 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_inds() {
        for (int i = 0; i < n; ) {
            if (count_both(i) < MAX_S) {
                inds.push_back(i);
                i++;
                continue;
            }

            int j = FIND_LARGEST(i, n - 1, [&](int j) { return count(j) == count(i); });
            i = j + 1;
        }
    }

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

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

        extract_inds();

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

        return -1;
    }
}

namespace SUB2B {
    const int MAX_BLOCK = 5000;
    vector<int> inds;
    int n, 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);
        int res = a[0] + a[1];
        if (res == 0)
            throw i;
        return res;
    }

    void extract_inds(int l, int r) {
        while (l <= r and count_both(l) < MAX_S)
            inds.push_back(l++);
        while (l <= r and count_both(r) < MAX_S)
            inds.push_back(r--);

        if (l > r)
            return;

        if (count(l) == count(r))
            return;

        for (int i = l; i <= r; ) {
            if (count_both(i) < MAX_S) {
                inds.push_back(i);
                i++;
                continue;
            }

            int j = FIND_LARGEST(i, r, [&](int j) { return count(j) == count(i); });
            i = j + 1;
        }
    }

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

        try {
            MAX_S = 0;
            for (int i = 0; i < n and i < 400; i++) {
                int s = count_both(i);
                maximise(MAX_S, s);
            }

            vector<pair<int, int>> ranges;
            for (int l = 0, r = MAX_BLOCK; l < n; l += MAX_BLOCK, r += MAX_BLOCK) {
                minimise(r, n - 1);
                ranges.emplace_back(l, r);
            }

            shuffle(ranges.begin(), ranges.end(), mt19937(999));

            for (const auto &range : ranges) {
                int l, r;
                tie(l, r) = range;
                extract_inds(l, r);
            }

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

        return -1;
    }
}

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

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