Submission #778541

#	Time	Username	Problem	Language	Result	Execution time	Memory
778541		benjaminkleyn	The Big Prize (IOI17_prize)	C++17	90 / 100	82 ms	2168 KiB

prize

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

bool asked[200000];
int L[200000], R[200000];
map<pair<int, int>, int> max_idx;

void Ask(int i)
{
    if (asked[200000]) return;
    asked[i] = true;
    vector<int> res = ask(i);
    L[i] = res[0], R[i] = res[1];
    if (max_idx.find(mp(L[i], R[i])) == max_idx.end())
        max_idx[mp(L[i], R[i])] = i;
    else
        max_idx[mp(L[i], R[i])] = max(max_idx[mp(L[i], R[i])], i);
}

int find_best(int n) 
{
    memset(asked, false, sizeof(asked));
    max_idx = map<pair<int,int>,int>();

    int i = 0;
    Ask(i);
    for (int j = 0; j < n && j < 500; j++)
    {
        Ask(j);
        if (L[j] + R[j] == 0)
            return j;
        if (L[j] + R[j] > L[i] + R[i])
            i = j;
    }
    int v = i;

    while (i < n)
    {
        for (int j = 18; j >= 0; j--)
            if (i + (1 << j) < n)
            {
                Ask(i + (1 << j));
                i = max_idx[mp(L[i], R[i])];
            }
        while (i < n)
        {
            Ask(++i);
            if (L[i] + R[i] == 0) return i;
            if (L[i] + R[i] == L[v] + R[v]) break;
        }
    }
    return n - 1;
}

Compilation message (stderr)

prize.cpp: In function 'void Ask(int)':
prize.cpp:12:21: warning: array subscript 200000 is above array bounds of 'bool [200000]' [-Warray-bounds]
   12 |     if (asked[200000]) return;
      |         ~~~~~~~~~~~~^
prize.cpp:6:6: note: while referencing 'asked'
    6 | bool asked[200000];
      |      ^~~~~

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