Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- //all of them are expensive
- if (fim - ini + 1 == qMen - (qL + qR))
- {
- for (int i = ini; i <= fim; i++)
- {
- vector<int> a = query(i);
- if (a[0]+a[1] == 0) return i;
- }
- 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);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
