제출 #703533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703533		SamNguyen	커다란 상품 (IOI17_prize)	C++14	90 / 100	76 ms	5296 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() {
        int cnt = 0;

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

            const int T = 2500;
            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>());

        MAX_S = 0;
        for (int i = 0; i < n and i < 500; 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;
    }
}

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

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