Submission #134504

#	Time	Username	Problem	Language	Result	Execution time	Memory
134504		tri	The Big Prize (IOI17_prize)	C++14	0 / 100	102 ms	252 KiB

prize

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

vi ask(int i);

int gGrt(int i) {
    vi ret = ask(i);
    return ret[0] + ret[1];
}

int maxG, ans = -1;

void search(int l, int r, int cnt, int lS, int rS) {
    if (ans != -1) {
        return;
    }
    if (l == r + 1) {
        return;
    }

    if (r - l + 1 == cnt) {
        for (int i = l; i <= r; i++) {
            if (gGrt(i) == 0) {
                ans = i;
                return;
            }
        }
        return;
    }

    int oMid = (l + r) / 2;
    int mid = oMid;
    vi ret = ask(mid);

    while (ret[0] + ret[1] != maxG) {
        if (ret[0] + ret[1] == 0) {
            ans = mid;
            return;
        }

        mid++;
        if (mid > r) {
            int found = mid - oMid;
            search(l, oMid - 1, cnt - found, lS, rS + found);
        }
        ret = ask(mid);
    }

    int found = mid - oMid;
    search(l, oMid - 1, ret[0] - found - lS, lS, ret[1] + found);
    search(mid + 1, r, ret[1] - rS, ret[0], rS);
}

int find_best(int N) {
    if (N < 4000) {
        for (int i = 0; i < N; i++) {
            if (gGrt(i) == 0) {
                return i;
            }
        }
    }

    int sqrt = 447;
    int tier = 473;
    int baseSub = 0;
    int maxG = 0;

    for (int i = 0; i < tier + 1; i++) {
        int grt = gGrt(i);
        if (grt == 0) {
            return i;
        }
        if (maxG == grt) {
            baseSub++;
        } else if (maxG < grt) {
            maxG = grt;
            baseSub = 1;
        }
    }
    int found = tier + 1 - baseSub;

    search(tier + 1, N - 1, maxG - found, found, 0);
    return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:77:9: warning: unused variable 'sqrt' [-Wunused-variable]
     int sqrt = 447;
         ^~~~

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