Submission #491736

#	Time	Username	Problem	Language	Result	Execution time	Memory
491736		qwerasdfzxcl	The Big Prize (IOI17_prize)	C++14	100 / 100	63 ms	1112 KiB

prize

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

using namespace std;
typedef long long ll;
const int MX = 475;
int X, ret = -1, val[200200];

void dnc(int l, int r, int valL, int valR){
    //printf("%d %d %d %d\n", l, r, valL, valR);
    int m = (l+r)>>1;
    vector<int> v;
    while(l<m){
        if (val[m]==-1 || val[m]==X){
            v = ask(m);
            val[m] = v[0]+v[1];
        }

        if (val[m]!=X){
            if (!val[m]) ret = m;
            --m;
            continue;
        }

        break;
    }

    if (l==m){
        m = (l+r)>>1;
        while(m<r){
            if (val[m]==-1 || val[m]==X){
                v = ask(m);
                val[m] = v[0]+v[1];
            }

            if (val[m]!=X){
                if (!val[m]) ret = m;
                ++m;
                continue;
            }

            break;
        }
    }

    if (r==m) return;
    if (v[0]!=valL) dnc(l, m, valL, v[1]);
    if (v[1]!=valR) dnc(m, r, v[0], valR);
}

int find_best(int n) {
    fill(val, val+n, -1);
    int i;
    for (i=0;i<min(n, MX+1);i++){
        auto v = ask(i);
        X = max(X, v[0]+v[1]);
        val[i] = v[0]+v[1];
        if (val[i]==0) ret = i;
        if (val[i]>=30) break;
    }

    dnc(i-1, n, i, 0);
    assert(ret!=-1);
    return ret;
}

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