Submission #778600

#	Time	Username	Problem	Language	Result	Execution time	Memory
778600		benjaminkleyn	The Big Prize (IOI17_prize)	C++17	96.13 / 100	87 ms	2112 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair

bool asked[200000];
int L[200000], R[200000];
int v, N;

vector<int> previous_queries;
void Ask(int i)
{
    if (asked[i]) return;
    asked[i] = true;
    previous_queries.push_back(i);
    vector<int> res = ask(i);
    L[i] = res[0], R[i] = res[1];
}

int find_best(int n) 
{
    memset(asked, false, sizeof(asked));

    N = n;

    int i = 0;
    while (i < n)
    {
        Ask(i);
        if (L[i] + R[i] == 0)
            return i;
        for (int j = 18; j >= 0; j--)
            if (i + (1 << j) < n)
            {
                bool bad_query = false;
                for (int x : previous_queries)
                    if (i <= x && x <= i + (1 << j) && (L[x] != L[i] || R[x] != R[i]))
                    {
                        bad_query = true;
                        break;
                    }
                if (bad_query) continue;
                Ask(i + (1 << j));
                if (L[i + (1 << j)] + R[i + (1 << j)] == 0)
                    return i + (1 << j);
                if (L[i + (1 << j)] == L[i] && R[i + (1 << j)] == R[i])
                    i += (1 << j);
            }
        i++;
    }
    return 0;
}

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