Submission #1173696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173696		n3rm1n	The Big Prize (IOI17_prize)	C++20	90 / 100	22 ms	2760 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
int asked[maxn], ansl[maxn], ansr[maxn];
vector < int > a;
void goask(int i)
{
    if(asked[i])
    {
        return;
    }
    a = ask(i);
    asked[i] = 1;
    ansl[i] = a[0];
    ansr[i] = a[1];
}

int find_best(int n)
{
    int maxsum = 0;
    for (int i = 0; i < min(n, 720); ++ i)
    {
        goask(i);
        int bigger = ansl[i] + ansr[i];
        if(bigger > maxsum)maxsum = bigger;
    }
    int start = 0, passed = 0;
    for (int i = 0; i < n; ++ i)
        {
            goask(i);
            int total = ansl[i] + ansr[i];
            if(total == 0)return i;
            if(total == maxsum)
            {
                start = i;
                break;
            }
            else
            {
                passed ++;
            }
        }

    for (int run = 1; run <= n; ++ run)
    {
        int l = start, r = n-1, mid, res = start;
        while(l <= r)
        {
            mid = (l + r)/2;
            goask(mid);
            int onl = ansl[mid];
            int onr = ansr[mid];
            int total = onl + onr;
            if(total == 0)return mid;
            if(total != maxsum)
            {
                r = mid - 1;
                res = mid - 1;
            }
            else if(onl == passed)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
                res = mid;
            }
        }
        for (int i = res + 1; i < n; ++ i)
        {
            goask(i);
            int total = ansl[i] + ansr[i];
            if(total == 0)return i;
            if(total == maxsum)
            {
                start = i;
                break;
            }
            else
            {
                passed ++;
            }
        }
    }
    return n-1;
}

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