oj.uz

Submission #1012662

# Submission time Handle Problem Language Result Execution time Memory
1012662 2024-07-02T13:15:07 Z ThegeekKnight16 The Big Prize (IOI17_prize) C++17
0 / 100
 678 ms 1048576 KB 
    #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, fim, qMen, aR[0], qR);
        if (x == -1) return dc(ini, mL, 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);
    }

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Runtime error 678 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Runtime error 658 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -