Submission #270804

#	Time	Username	Problem	Language	Result	Execution time	Memory
270804		hamerin	The Big Prize (IOI17_prize)	C++17	97.27 / 100	65 ms	5500 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

vector<vector<int>> cache;
vector<int> neoask(int i) {
    if (cache[i].empty()) return cache[i] = ask(i);
    return cache[i];
}

int minDeter = 0;
void solve(int s, int e, vector<bool> &mask) {
    if (s > e) return;

    auto vs = neoask(s);
    if (vs[0] + vs[1] != minDeter) {
        mask[s] = true;
        solve(s + 1, e, mask);
        return;
    }

    auto ve = neoask(e);
    if (ve[0] + ve[1] != minDeter) {
        mask[e] = true;
        solve(s, e - 1, mask);
        return;
    }

    if (e - s <= 1) return;
    if (vs[0] == ve[0]) return;

    int m = (s + e) >> 1;
    auto vm = neoask(m);
    if (vm[0] + vm[1] != minDeter) mask[m] = true;
    solve(s, m, mask);
    solve(m, e, mask);
}

int find_best(int n) {
    if (n <= 5000) {
        for (int i = 0; i < n; i++) {
            auto v = ask(i);
            if (v[0] + v[1] == 0) return i;
        }
    }

    vector<bool> mask(n);
    cache.resize(n);

    // 473번 해보기
    for (int i = 0; i < 170; i++) {
        cache[i] = ask(i);
        minDeter = max(minDeter, cache[i][0] + cache[i][1]);
    }
    for (int i = n - 170; i < n; i++) {
        cache[i] = ask(i);
        minDeter = max(minDeter, cache[i][0] + cache[i][1]);
    }
    for (int i = (n / 2) - 76; i <= (n / 2) + 76; i++) {
        cache[i] = ask(i);
        minDeter = max(minDeter, cache[i][0] + cache[i][1]);
    }

    solve(0, n - 1, mask);

    for (int i = 0; i < n; i++) {
        if (!mask[i]) continue;

        auto v = neoask(i);
        if (v[0] + v[1] == 0) return i;
    }

    return 0;
}

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