제출 #778518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
778518		benjaminkleyn	커다란 상품 (IOI17_prize)	C++17	90 / 100	84 ms	5240 KiB

prize

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

vector<int> mem[200000];
vector<int> Ask(int i)
{
    if (mem[i].size()) return mem[i];
    return mem[i] = ask(i);
}

int find_best(int n) 
{
    int i = 0;
    vector<int> cur = Ask(i);
    for (int j = 0; j < n && j < 500; j++)
    {
        vector<int> res = Ask(j);
        if (res[0] + res[1] == 0)
            return j;
        if (res[0] + res[1] > cur[0] + cur[1])
            i = j, cur = res;
    }

    while (i < n)
    {
        for (int j = 18; j >= 0; j--)
            if (i + (1 << j) < n)
            {
                vector<int> res = Ask(i + (1 << j));
                if (res[0] == cur[0] && res[1] == cur[1])
                    i += (1 << j);
            }
        while (i < n)
        {
            vector<int> res = Ask(++i);
            if (res[0] + res[1] == 0) return i;
            if (cur[0] + cur[1] == res[0] + res[1])
            {
                cur = res;
                break;
            }
        }
    }
    return n - 1;
}

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