Submission #1012770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012770		ThegeekKnight16	The Big Prize (IOI17_prize)	C++17	100 / 100	32 ms	1684 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 (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;
            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 (stderr)

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

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