# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
946298 | Pikachu | The Big Prize (IOI17_prize) | C++17 | 61 ms | 3420 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
template<typename T>
inline bool maxi(T &x, const T &val)
{
if (x < val) return x = val, true;
return false;
}
template<typename T>
inline bool mini(T &x, const T &val)
{
if (x > val) return x = val, true;
return false;
}
map<int,pair<int,int> > mp[500];
int RandInt(int l, int r)
{
int ans = 0;
for (int i = 0; i < 2; i++) {
ans = (ans << 15) | (rand() & ((1 << 15) - 1));
}
return ans % (r - l + 1) + l;
}
const int maxn = 2e5 + 10;
pair<int,int> dak[maxn];
bool done;
int res;
int cntask;
pair<int,int> myask(int x)
{
if (done) return make_pair(-1, -1);
if (dak[x].first != -1) return dak[x];
// cntask++;
// if (cntask > 10000) assert(false);
vector<int> tmp = ask(x - 1);
if (tmp[0] + tmp[1] == 0) {
res = x - 1;
done = true;
}
dak[x] = make_pair(tmp[0], tmp[1]);
mp[tmp[0] + tmp[1]][x] = dak[x];
return dak[x];
}
int find_best(int n)
{
srand(time(0));
memset(dak, -1, sizeof dak);
int maxx = 0;
int test = 100;
while (test--) {
int x = RandInt(1, n);
pair<int,int> tmp = myask(x);
maxi(maxx, tmp.first + tmp.second);
}
int cur = 1;
while (!done) {
pair<int,int> tmp = myask(cur);
if (tmp.first + tmp.second != maxx) cur++;
else break;
}
while (!done) {
if (myask(cur).second == 0) break;
if (myask(cur).second == n - cur) {
for (int i = cur + 1; i <= n; i++) {
myask(i);
}
break;
}
auto it = mp[maxx].upper_bound(cur);
int nex = n;
if (it != mp[maxx].end()) {
nex = it -> first;
if (it -> second.second == mp[maxx][cur].second) {
cur = nex;
continue;
}
}
int mid = (cur + nex) >> 1;
while (!done) {
pair<int,int> tmp = myask(mid);
if (tmp.first + tmp.second != maxx) mid--;
else break;
}
if (mid == cur) {
mid = (cur + nex) >> 1;
while (!done) {
pair<int,int> tmp = myask(mid);
if (tmp.first + tmp.second != maxx) mid++;
else break;
}
if (mid == nex) {
cur = nex;
}
else {
cur = mid;
}
continue;
}
}
return res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |