Submission #221802

#	Time	Username	Problem	Language	Result	Execution time	Memory
221802		patrikpavic2	The Big Prize (IOI17_prize)	C++17	100 / 100	57 ms	2136 KiB

prize

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  prize
* score: 100.0
* date:  2019-06-16 09:02:45.353752
*/
#include "prize.h"
#include <vector>
#include <algorithm>
#include <cstring>

#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 2e5 + 500;

int L[N], R[N];

int get_L(int i){
    if(L[i] != -1) return L[i];
    vi res = ask(i);
    L[i] = res[0], R[i] = res[1];
    return L[i];
}

int get_R(int i){
    if(L[i] != -1) return R[i];
    vi res = ask(i);
    L[i] = res[0], R[i] = res[1];
    return R[i];
}

int loli;
vi svi;

void solve(int l,int r){
    if(l > r) return;
    if(get_L(l) + get_R(l) < loli){
        svi.PB(l); solve(l + 1, r);
        return;
    }
    if(l == r) return;
    if(get_L(r) + get_R(r) < loli){
        svi.PB(r); solve(l, r - 1);
        return;
    }
    if(get_L(l) == get_L(r) || l + 1 == r) return;
    solve(l, (l + r) / 2);
    solve((l + r) / 2, r);
}


int find_best(int n) {
    memset(L, -1, sizeof(L));
    svi.clear();
	loli = 0;
	for(int i = 0;i < 100;i++){
        int x = (rand() + rand()) % n;
        x = (x % n + n) % n;
        loli = max(loli, get_L(x) + get_R(x));
	}
    solve(0, n - 1);
    for(int x : svi){
        if(get_L(x) + get_R(x) == 0)
            return x;
    }
	return 0;
}

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