Submission #1218514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218514		andrej246	The Big Prize (IOI17_prize)	C++20	100 / 100	26 ms	11420 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;

#define NL "\n"
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(v);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

vector<vector<int>> cache;

vector<int> askc(ll i) {
    if (cache[i][0] != -1) return cache[i];
    else return cache[i] = ask(i);
}

vl find_all(ll x, ll y, ll fullcount) {
    vl ans;
    if (x > y) return {};
    auto a1 = askc(x);
    auto a2 = askc(y);
    if (a1[0]+a1[1] < fullcount) {
        ans.push_back(x);
        for (auto k: find_all(x+1,y,fullcount)) ans.push_back(k);
        return ans;
    }
    if (a2[0]+a2[1] < fullcount) {
        ans.push_back(y);
        for (auto k: find_all(x,y-1,fullcount)) ans.push_back(k);
        return ans;
    }
    if (a1[0] == a2[0]) return {};

    ll l = x;
    ll r = y+1;
    while (l+1 < r) {
        ll m = (l+r)/2;
        auto re = askc(m);
        if (re[0]+re[1] < fullcount) {
            l = m;
            break;
        }
        if (re[0] > a1[0]) r = m;
        else l = m;
    }
    ans.push_back(l);
    for (auto k: find_all(x,l-1,fullcount)) ans.push_back(k);
    for (auto k: find_all(l+1,y,fullcount)) ans.push_back(k);
    return ans;
}


int find_best(int n) {

    ll block = 1;
    while (block*block < n) block++;
    if (block*block >= n) block--;
    assert(block*block < n);

    FOR(i,n) cache.push_back({-1,-1});
    ll fullcount = 0;
    vl indices;
    vl lcounts;
    vl fcounts;
    ll cur = 0;

    ll ans = -1;
    while (cur < n) {
        auto re = askc(cur);
        indices.push_back(cur);
        lcounts.push_back(re[0]);
        fcounts.push_back(re[0]+re[1]);
        fullcount = max(fullcount,fcounts.back());
        cur += block;
    }
    fcounts[0] = fullcount;

    if (indices.back() != n-1) indices.push_back(n-1);
    fcounts.push_back(fullcount);
    lcounts.push_back(fullcount);
    ll pi = -1;
    FOR(i,(ll)indices.size()) {
        if (fcounts[i] == -1) continue;
        if (pi == -1) {
            pi = i;
            continue;
        }

        ll x = indices[pi];
        ll y = indices[i];
        for (auto k: find_all(x,y,fullcount)) {
            auto a = askc(k);
            if (a[0] + a[1] == 0) {
                ans = k;
                break;
            }
        }

        pi = i;
        if (ans != -1) break;
    }

    assert(ans != -1);
    
    auto a = askc(ans);
    assert(a[0]+a[1] == 0);

    // if (ans == -1) {
    //     FOR(i,n) {
    //         if (cache[i][0]+cache[i][1] == 0) ans = i;
    //     }
    // }
    
    return ans;

}

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