Submission #946298

#	Time	Username	Problem	Language	Result	Execution time	Memory
946298		Pikachu	The Big Prize (IOI17_prize)	C++17	20 / 100	61 ms	3420 KiB

prize

#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)

prize.cpp: In function 'int find_best(int)':
prize.cpp:56:31: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   56 |     memset(dak, -1, sizeof dak);
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

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