Submission #1173681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173681		n3rm1n	The Big Prize (IOI17_prize)	C++20	0 / 100	2 ms	440 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, 750); ++ i)
	{
        goask(i);
        int bigger = ansl[i] + ansr[i];
        if(bigger > maxsum)maxsum = bigger;
	}
	int start = 0, passed = 0;
	for (int run = 1; run < n; ++ run)
    {
        int l = start, r = n-1, mid, res = 0;
        while(l <= r)
        {
            mid = (l + r)/2;
            goask(mid);
            int onl = ansl[mid];
            int onr = ansr[mid];
            int total = onl + onr;
            if(total == 1)return mid;
            if(total != maxsum)
            {
                r = 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 == 1)return i;
            if(total == maxsum)
            {
                start = i;
            }
            else
            {
                passed ++;
            }
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

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