Submission #1134144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134144		jerzyk	The Big Prize (IOI17_prize)	C++20	100 / 100	11 ms	420 KiB

prize

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
int tab[N], il = 0;

int Find(int p, int k, int l, int r)
{
    if(l + r == il) return -1;
    if(p > k) return -1;
    vector<int> w;
    int s = (p + k) / 2;
    int s1 = s;
    bool xd = 1;
    do
    {
        w = ask(s);
        if(w[0] + w[1] == 0) return s;
        if(w[0] + w[1] == il) xd = 0;
        if(s == k) break;
        if(xd) ++s;
    }while(xd);
    //cerr << p << " " << k << " " << l << " " << r << "\n";
    int d = s - s1;
    if(xd)
        return Find(p, s1 - 1, l, r + d);
    int a = -1;
    a = Find(s + 1, k, w[0], r);
    if(a > -1) return a;
    a = Find(p, s1 - 1, l, w[1] + d);
    return a;
}

ll F(ll a)
{
    return (a * a + 1LL);
}

bool Check(ll x, ll n)
{
    ll a = x / 2;
    if(x + F(a) + F(F(a)) > n) return true;
    return false;
}

int find_best(int n)
{
    vector<int> w;
    int s = 0;
    int d = 2 * (int)sqrt(n); int nn = max(1, n - d);
    int i = n - 1;
    while(i >= nn)
    {
        w = ask(i);
        if(w[0] + w[1] == 0) return i;
        if(w[0] + w[1] > il)
            {s = 0;}
        il = max(il, w[0] + w[1]);
        if(w[0] + w[1] == il)
            ++s;

        --i;
        if(Check(w[0] + w[1], n)) break;
    }
    nn = i + 1;
    s = (n - nn) - s;
    int ans = Find(0, nn - 1, 0, s);
    return ans;
}

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