Submission #112259

#	Time	Username	Problem	Language	Result	Execution time	Memory
112259		someone_aa	The Big Prize (IOI17_prize)	C++17	97.85 / 100	61 ms	2192 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int maxn = 200100;
bool visited[maxn];
int q[maxn][2];
int max_sum, ind;
P query(int i) {
    if(visited[i]) return {q[i][0], q[i][1]};
    visited[i] = true;
    vector<int>curr = ask(i);
    q[i][0] = curr[0];
    q[i][1] = curr[1];
    return {q[i][0], q[i][1]};
}

int sum(int i) {
    query(i);
    return q[i][0] + q[i][1];
}

void solve(int l, int r) {
    //cout<<l<<" "<<r<<"\n";
    if(l > r || ind != -1) return;

    P ql = query(l);
    P qr = query(r);

    int suml = ql.first + ql.second;
    int sumr = qr.first + qr.second;

    if(suml == 0) {
        ind = l;
        return;
    }

    if(sumr == 0) {
        ind = r;
        return;
    }

    if(ql.second == 0 || qr.first == 0) return;

    if(l == r) return;

    if(suml != max_sum) {
        solve(l+1, r);
        return;
    }

    if(sumr != max_sum) {
        solve(l, r-1);
        return;
    }

    int between  = qr.first - ql.first;
    if(between == 0) return;

    int mid = (l + r) / 2;

    solve(l, mid);
    solve(mid, r);
}

int find_best(int n) {
    ind = -1;

    int b = sqrt(n) + 1;
    b = min(n, b);

    mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> uid(0, n - 1);

    for(int i=0;i-b<n;i+=b) {
        int x = min(i, n-1);
        if(sum(x) == 0) return x;
        max_sum = max(max_sum, sum(x));
    } //max_sum = 1;

    for(int i=0;i<100;i++) {
        int pos = uid(g);
        if(sum(pos) == 0) return pos;
        max_sum = max(max_sum, sum(pos));
    }

    for(int l=0;l<n;l+=b) {
        int r = min(n-1, l+b-1);
        solve(l, r);
    }
    return ind;
}

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