Submission #407000

#	Time	Username	Problem	Language	Result	Execution time	Memory
407000		dxz05	The Big Prize (IOI17_prize)	C++14	20 / 100	31 ms	35644 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 3e2;
typedef long long ll;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int foo, hoo;

vector<int> asked_values[MAXN];

set<int> indexes[MAXN];

void ASK(int i){
    vector<int> res;
    if (asked_values[i].empty()){
        res = ask(i);
        //cout << i << ' ' << res.front() << ' ' << res.back() << endl;
    } else res = asked_values[i];

    foo = res.front();
    hoo = res.back();
    asked_values[i] = res;

    indexes[foo + hoo].insert(i);

}


int get(int i, int r){
    ASK(r);
    if (*indexes[foo + hoo].begin() == r) return foo;
    int l = *prev(indexes[foo + hoo].upper_bound(i));
    r = foo;
    ASK(l);
    l = foo;
    return r - l;
}

int find_best(int n) {
    int mx = 0;
    for (int i = 0; i < min(n, 500); i++){
        ASK(i);
        if (foo + hoo == 0) return i;
        mx = max(mx, foo + hoo);
    }

    map<int, int> mp;
	for (int i = 0; i < n; i++){

        int l = i, r = n - 1;
        int nxt = n;

        while (l <= r){
            int m = (l + r) >> 1;
            ASK(m);

            if (foo + hoo == 0) return m;

            if (foo + hoo < mx) nxt = m;

            if (get(i, m)){
                r = m - 1;
            } else l = m + 1;

        }

        i = nxt;
        if (i == n) break;
        ASK(i);

        for (auto &now : mp){
            if (now.first >= foo + hoo) now.second++;
        }

        if (mp.find(foo + hoo) == mp.end()) mp[foo + hoo] = 1;

	}

    for (int i = n - 1; i >= n - 200; i--){
        if (i < 0) break;
        ASK(i);
        if (foo + hoo == 0) return i;
    }

	return n / 2;
}

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