제출 #798240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798240		PixelCat	커다란 상품 (IOI17_prize)	C++14	20 / 100	8 ms	6760 KiB

prize

#include "prize.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
mt19937_64 rng(48763);

pii mem[MAXN + 10];
pii qry(int idx) {
    if(mem[idx].F != -1) return mem[idx];
    auto res = ask(idx);
    return mem[idx] = pii(res[0], res[1]);
}

int solve(vector<int> v) {
    // for(auto &i:v) cerr << i << " ";
    // cerr << "\n";

    if(sz(v) == 1) return v[0];
    
    int len = sz(v);
    int tot = 0;
    if(len >= 100) {
        For(_, 1, 100) {
            pii p = qry(v[rng() % len]);
            tot = max(tot, p.F + p.S);
        }
    } else {
        for(auto &i:v) {
            pii p = qry(i);
            tot = max(tot, p.F + p.S);
        }
    }
    
    vector<int> res;
    For(i, 0, tot - 1) {
        int lo, hi = len;
        if(!sz(res)) lo = -1;
        else lo = res.back();
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            pii p = qry(v[mi]);
            if(p.F + p.S < tot || p.F > i) hi = mi;
            else lo = mi;
        }
        assert(hi < len);
        res.eb(v[hi]);
    }

    return solve(res);
}

i32 find_best(i32 n) {
    fill(mem, mem + MAXN + 10, pii(-1, -1));
    vector<int> v(n);
    For(i, 0, n - 1) v[i] = i;
    return solve(v);
}

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