Submission #1045379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045379		Trent	The Big Prize (IOI17_prize)	C++17	96.04 / 100	40 ms	1648 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;

#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
struct pii{int a, b;};
typedef vector<int> vi;
vi getVal(int i, map<int, vi>& cache) {
    if(cache.count(i)) return cache[i];
    return cache[i] = ask(i);
}

void getBetter(int l, int r, int loid, int lOff, int rOff, map<int, vi>& cache) {
    assert(l <= r);
    int mid = (l + r) / 2;
    REP(ci, mid, r+1) {
        vi cv = getVal(ci, cache);
        if(cv[0] + cv[1] == loid) {
            if(cv[0] + lOff > 0) getBetter(l, ci - 1, loid, lOff, -cv[1], cache);
            if(cv[1] + rOff > 0) getBetter(ci+1, r, loid, -cv[0], rOff, cache);
            return; 
        }
    }
    for(int ci = mid - 1; ci >= l; --ci) {
        vi cv = getVal(ci, cache);
        if(cv[0] + cv[1] == loid) {
            if(cv[0] + lOff > 0) getBetter(l, ci - 1, loid, lOff, -cv[1], cache);
            if(cv[1] + rOff > 0) getBetter(ci+1, r, loid, -cv[0], rOff, cache);
            return; 
        }
    }
}

const int MV = 500;
int find_best(int n){
    map<int, vi> ca;
    forR(i, min(n, MV)) getVal(i, ca);
    int loVal = ca[0][0] + ca[0][1];
    forR(i, min(n, MV)) loVal = max(loVal, ca[i][0] + ca[i][1]);
    getBetter(0, n-1, loVal, 0, 0, ca);
    int bi = -1;
    for(auto [ci, cv] : ca) if(cv[0] + cv[1] == 0) {
        bi = ci;
    }
    assert(bi != -1);
    return bi;
}

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