Submission #703577

#	Time	Username	Problem	Language	Result	Execution time	Memory
703577		SamNguyen	The Big Prize (IOI17_prize)	C++14	90 / 100	73 ms	5304 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 {
    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) {
                i++;
                continue;
            }

            int k = FIND_LARGEST(0, log2(n - i) + 1, [&](int k) {
                return i + (1 << k) < n and count(i + (1 << k)) == count(i);
            });

//            cerr << "i = " << i << " -> k = " << k << endl;

            while (k >= 0) {
                if (i + (1 << k) < n and count(i + (1 << k)) == count(i))
                    i += 1 << k;
                k--;
            }

            cnt++;
            i++;
        }

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

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

        try {
            MAX_S = 0;
            for (int i = 0; i < 3 and i < n; i++)
                maximise(MAX_S, count_both(i));
            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: 70 / 80