Submission #420707

#	Time	Username	Problem	Language	Result	Execution time	Memory
420707		Andyvanh1	The Big Prize (IOI17_prize)	C++14	98.05 / 100	75 ms	2780 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
 
using namespace std;
 
#define vt vector
#define INF 0x3f3f3f3f
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,x) for(int (i) = 0;(i) < (x); (i)++)
#define MOD 1000000007
 
typedef vt<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
pii got[200005];
 
 
int fotal = 0;
 
int consum(int l, int r, int minl, int minr) {
    if (r < l)
        return -1;
 
    int mid = (l + r) >> 1;
    vi a;
 
    if (got[mid] != make_pair(-1, -1))
        a = {got[mid].first, got[mid].second};
    else
        a = ask(mid);
 
 
    if (a[0] + a[1] == fotal) {
        a[0] -= minl;
        a[1] -= minr;
        int x = -1, y = -1;
 
        if (a[0] != 0)
            x = consum(l, mid - 1, minl, a[1] + minr);
 
        if (x != -1)
            return x;
 
        if (a[1] != 0)
            y = consum(mid + 1, r, minl + a[0], minr);
 
        return max(x, y);
    } else if (a[0] + a[1] == 0) {
        return mid;
    } else {
        int cur1 = mid - 1;
        int cur2 = mid + 1;
        int has = 1;
 
        while (cur2 <= r) {
            if (got[cur2] != make_pair(-1, -1))
                a = {got[cur2].first, got[cur2].second};
            else
                a = ask(cur2);
 
            if (a[0] + a[1] == fotal) {
                int x = -1, y = -1;
 
                if (a[0] - minl - has != 0)
                    x = consum(l, mid - 1, minl, a[1] + has);
 
                if (x != -1)
                    return x;
 
                if (a[1] - minr != 0)
                    y = consum(cur2 + 1, r, a[0], minr);
 
                return max(x, y);
            } else if (a[0] + a[1] == 0) {
                return cur2;
            } else {
                cur2++;
                has++;
            }
        }
 
        while (cur1 >= l) {
            if (got[cur1] != make_pair(-1, -1))
                a = {got[cur1].first, got[cur1].second};
            else
                a = ask(cur1);
 
            if (a[0] + a[1] == fotal) {
                if (a[0] - minl != 0)
                    return consum(l, cur1 - 1, minl, a[1]);
                else
                    return -1;
            } else if (a[0] + a[1] == 0) {
                return cur1;
            } else {
                cur1--;
            }
 
        }
 
        return -1;
 
    }
}
 
int find_best(int n) {
    vi arr(n);
 
    for (int i = 0; i < n; i++) {
        got[i] = {-1, -1};
        arr[i] = i;
    }
 
    random_shuffle(all(arr));
 
    int k = sqrt(n) + 2;
 
    for (int i = 0; i < k; i++) {
        int j = arr[i];
        vi a = ask(j);
        got[j] = {a[0], a[1]};
 
        if (a[0] + a[1] == 0)
            return j;
 
        if (a[0] + a[1] > fotal)
            fotal = a[0] + a[1];
    }
 
    return consum(0, n - 1, 0, 0);
}

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