Submission #798402

#	Time	Username	Problem	Language	Result	Execution time	Memory
798402		HaroldVemeno	The Big Prize (IOI17_prize)	C++17	97.41 / 100	44 ms	296 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 = 2*sqrt(n);
	for(int i = 0; i < min(n, 500); i++) {
		vector<int> res = ask(i);
        if(res[0] + res[1] == 0) return i;
	    ec = max(res[0] + res[1], ec);
	}

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

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:33:9: warning: unused variable 'sn' [-Wunused-variable]
   33 |     int sn = 2*sqrt(n);
      |         ^~

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