Submission #798368

#	Time	Username	Problem	Language	Result	Execution time	Memory
798368		HaroldVemeno	The Big Prize (IOI17_prize)	C++17	20 / 100	83 ms	336 KiB

prize

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

using namespace std;

int ec = 0;
int n;

int sift(int l, int r, int e, int le, int re) {
    if(e <= 0) return -1;

    int m = (l+r)/2;
    int mr = m;
    vector<int> mra;
    for(mr = m; mr < r; ++mr) {
        mra = ask(mr);
        if(mra[0] + mra[1] == ec) {

            break;
        } else if(mra[0] + mra[1] == 0) {
            return mr;
        }
    }
    if(mr == r) {
        return sift(l, m, e - (mr - m), le, re + (mr - m));
    }
    return max(sift(l, m, mra[0] - le - (mr - m), le, (mr - m) + mra[1]),
               sift(mr+1, r, mra[1] - re, mra[0], re));
}

int find_best(int N) {
    n = N;
    int sn = sqrt(n);
	for(int i = 0; i < sn+1; i++) {
		vector<int> res = ask(i);
	    ec = max(res[0] + res[1], ec);
	}

    return sift(0, n, ec, 0, 0);
}

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