Submission #1143888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143888		Rainmaker2627	The Big Prize (IOI17_prize)	C++20	100 / 100	15 ms	5520 KiB

prize

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

bool visited[200000];
vector<int> res[200000];
int ans=-1, lol=0;

vector<int> query(int pos) {
    if (visited[pos]) return res[pos];
    visited[pos] = true;
    res[pos] = ask(pos);
    if (res[pos][0]+res[pos][1]==0) throw pos;
    return res[pos];
}

void search(int l, int r, int nl, int nr) {
    for (int i = 0; i < r-l+1; i++) {
        int mid, midl=(l+r)/2-i/2, midr=(l+r)/2+(i+1)/2;
        if (i%2) mid=midr;
        else mid=midl;
        auto x=query(mid);
        if (x[0]+x[1]==lol) {
            int xl=(i%2?midr-midl:0), xr=(i%2?0:midr-midl);
            if (x[0]-xl>nl) search(l, midl-1, nl, x[1]+xl);
            if (x[1]-xr>nr) search(midr+1, r, x[0]+xr, nr);
            break;
        }
    }
}

int find_best(int n) {
    try {
        int p=0;
        for (int i = 0; i < 474 && i < n && lol < 27; i++) {
            auto x=query(i);
            if (x[0]+x[1]>lol) p=i, lol=x[0]+x[1];
        } search(p, n-1, p, 0);
        return ans;
    } catch (int ans) {
        return ans;
    } return -1;
}

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