제출 #213375

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

prize

#include "prize.h"
#include <algorithm>
#include <iostream>
#include <chrono>
#include <random>
#include <vector>
using namespace std;
#ifdef MANSON
mt19937 rng(305);
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif // MANSON

namespace
{
    const int maxN = 200000;
    int n;

    vector<int> cache[maxN];
    inline vector<int> Ask(int i)
    {
        if (cache[i].size()) return cache[i];
        return cache[i] = ask(i);
    }
    int mx = 0;
    inline bool Cheapest(int i)
    {
        vector<int> res = Ask(i);
        bool f = (res[0] + res[1] == mx);
        // cerr << i << " is" << (f ? " " : "n't ") << " a cheapy.\n";
        return f;
    }
    int Solve(int l, int r)
    {
        while (l <= r && !Cheapest(l))
        {
            vector<int> res = Ask(l);
            if (res[0] + res[1] == 0) return l;
            ++l;
        }
        while (l <= r && !Cheapest(r))
        {
            vector<int> res = Ask(r);
            if (res[0] + res[1] == 0) return r;
            --r;
        }
        if (l >= r) return -1;
        vector<int> res1 = Ask(l), res2 = Ask(r);
        if (res1[1] == res2[1]) return -1;
        int m = (l + r) / 2;
        int x = Solve(m + 1, r);
        if (x != -1) return x;
        return Solve(l, m);
    }
}

int find_best(int n_) {
    n = n_;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    shuffle(p.begin(), p.end(), rng);
    if (p.size() > 500) p.erase(p.begin() + 500, p.end());
    for (int i: p)
    {
        vector<int> res = Ask(i);
        mx = max(mx, res[0] + res[1]);
    }
    return Solve(0, n - 1);
}

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