제출 #1012330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012330		ThegeekKnight16	커다란 상품 (IOI17_prize)	C++17	20 / 100	61 ms	1556 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int Q = 10000;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
map<int, vector<int>> ans;

vector<int> query(int x)
{
    if (ans.count(x)) return ans[x];
    return ans[x] = ask(x);
}

int dc(int ini, int fim, int qMen, int qL, int qR)
{
    // cerr << "ini: " << ini << ", fim: " << fim << '\n';
    if (ini > fim || qL + qR == qMen) return -1;
    if (qMen - (qL + qR) == fim - ini + 1)
    {
        for (int i = ini; i <= fim; i++)
        {
            vector<int> a = query(i);
            if (a[0]+a[1] == 0) return i;
        }
        return -1;
    }
    int mL = (ini+fim)>>1, mR = (ini+fim)>>1;
    vector<int> aL, aR;
    bool excludeL = 0, excludeD = 0;
    while (mL >= ini)
    {
        aL = query(mL);
        if (aL[0]+aL[1] == 0) return mL;
        if (aL[0]+aL[1] < qMen) --mL;
        else break;
    }
    while (mR <= fim)
    {
        aR = query(mR);
        if (aR[0]+aR[1] == 0) return mR;
        if (aR[0]+aR[1] < qMen) ++mR;
        else break;
    }

    int x = dc(mR+1, fim, qMen, aR[0], qR);
    if (x == -1) return dc(ini, mL-1, qMen, qL, aL[1]);
    return x;

}

int find_best(int n)
{
    // if (n <= 5000)
    // {
    //     vector<int> ids(n); iota(ids.begin(), ids.end(), 0);
    //     shuffle(ids.begin(), ids.end(), rng);
    //     for (auto i : ids)
    //     {
    //         vector<int> a = query(i);
    //         if (a[0]+a[1] == 0) return i;
    //     }
    // }
    vector<int> ids;
    for (int i = 0; i < 10; i++) ids.push_back(uniform_int_distribution<int>(0, n-1)(rng));
    vector<vector<int>> possQ;
    for (auto x : ids) possQ.push_back(query(x));
    int qMen = 1;
    for (auto &x : possQ) qMen = max(qMen, x[0]+x[1]);
    return dc(0, n-1, qMen, 0, 0);
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int dc(int, int, int, int, int)':
prize.cpp:29:10: warning: unused variable 'excludeL' [-Wunused-variable]
   29 |     bool excludeL = 0, excludeD = 0;
      |          ^~~~~~~~
prize.cpp:29:24: warning: unused variable 'excludeD' [-Wunused-variable]
   29 |     bool excludeL = 0, excludeD = 0;
      |                        ^~~~~~~~

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