Submission #703544

#	Time	Username	Problem	Language	Result	Execution time	Memory
703544		SamNguyen	The Big Prize (IOI17_prize)	C++14	98.11 / 100	53 ms	5288 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);
        int res = a[0] + a[1];
        if (res == 0)
            throw i;
        return res;
    }

    void extract_inds() {
        int cnt = 0;

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

            const int T = 990;
            int j = FIND_LARGEST(i, min(n - 1, i + T), [&](int j) { return count(j) == count(i); });
//            if (j > i + T)
//                cout << "Nah." << endl;

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

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

            i = j + 1;
        }

//        cout << "cnt = " << cnt << endl;
    }

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

        try {
            MAX_S = count_both(0);
            extract_inds();
        }
        catch (int i) {
            return i;
        }
        return -1;
    }
}

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

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