Submission #162335

#	Time	Username	Problem	Language	Result	Execution time	Memory
162335		popovicirobert	The Big Prize (IOI17_prize)	C++14	20 / 100	109 ms	10416 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 2e5;

static bool mark[MAXN];
vector <int> qry[MAXN];

inline vector <int> myask(int pos) {
    if(mark[pos] == 0) {
        qry[pos] = ask(pos);
    }
    mark[pos] = 1;
    return qry[pos];
}

int find_best(int n) {
    srand(time(NULL));

    auto myrand = [&]() {
        return (1LL * (1LL << 15) * rand() + rand()) % n;
    };

    vector <bool> vis(n);
    int i, mx = 0;

    for(i = 0; i < 100 && i < n; i++) {
        int cur = myrand();
        while(vis[cur]) {
            cur = myrand();
        }
        vector <int> a = myask(cur);
        mx = max(mx, a[0] + a[1]);
        vis[cur] = 1;
    }

    int num = n - mx;
    i = 0;
    while(i < n) {
        vector <int> a = myask(i);
        if(a[0] + a[1] == 0) {
            return i;
        }
        if(a[0] + a[1] < mx) {
            while(1) {
                a = myask(++i);
                if(a[0] + a[1] == 0) {
                    return i;
                }
                if(a[0] + a[1] == mx) break;
            }
        }
        else {
            if(a[0] + a[1] > mx) {
                assert(0);
            }
            int l = a[0], r = a[1];
            int res = 0;
            for(int step = 1 << 17; step; step >>= 1) {
                if(i + res + step < n && num >= res + step + 1) {
                    a = myask(i + res + step);
                    if(a[0] == l && a[1] == r) {
                        res += step;
                    }
                }
            }
            i += res + 1;
            num -= (res + 1);
        }
    }

    assert(0);
}

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