oj.uz

답안 #1012777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012777 2024-07-02T15:09:11 Z ThegeekKnight16 커다란 상품 (IOI17_prize) C++17
0 / 100
 0 ms 344 KB 
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
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)
{
    //Cases in which i don't have to test
    if (ini > fim || qL + qR == qMen) return -1;
    if (fim - ini >= 1)
    {
        vector<int> aL = query(ini), aR = query(fim);
        if (aL[0]+aL[1] == 0) return ini;
        if (aR[0]+aR[1] == 0) return fim;
        return -1;
    }
    if (query(ini) == query(fim)) return -1;

    //get middle expensive
    int mL = (ini+fim)>>1, mR = (ini+fim)>>1;
    vector<int> aL, aR;
    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;
    }

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

}

int find_best(int n)
{
    //here to find expensive quantity -> P(expensive) ~ 1/sqrt(N)
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    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);
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Integer -1 violates the range [0, 199999]
2 Halted 0 ms 0 KB -