Submission #805237

#	Time	Username	Problem	Language	Result	Execution time	Memory
805237		HaroldVemeno	The Big Prize (IOI17_prize)	C++17	97.80 / 100	50 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 - (r - m), le, re + (r - 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);
    int skp = 1;
    while(sn > 1) {
        skp += sn;
        sn = sqrt(sn);
    }
    srand(9399390);
	for(int i = 0; i < min(n, skp); i++) {
        int r = rand() % n;
		vector<int> res = ask(r);
        if(res[0] + res[1] == 0) return r;
	    ec = max(res[0] + res[1], ec);
	}

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

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