Submission #1147595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147595		iah	The Big Prize (IOI17_prize)	C++20	98.04 / 100	16 ms	5264 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

void myAssert(bool a) {
  while (!a) {
    assert(-1 == 1);
  }
}

const int nmax = 2e5;
vector < int > sv[nmax + 7], val;
int cnt = 1, used[nmax + 7];

vector < int > myAsk(int i) {
  if (sv[i].empty()) {
    ++ cnt;
    myAssert(cnt <= 10000);
    sv[i] = ask(i);
    int sum = sv[i][0] + sv[i][1];
    bool ok = 1;
    for (auto x: val) {
      if (x == sum) {
        ok = 0;
      }
    }
    if (ok) {
      val.push_back(sum);
      sort(val.begin(), val.end(), greater < int > ());
    }
  }

  return sv[i];
}

int maxVal(int n, int v) {
  int res = n, remain = n;
  for (auto x: val) {
    int cur = remain - x;
    remain -= cur;
    if (x == v) {
      continue;
    }
    res -= cur;
//    cout << x << " " << remain << " " << res << "\n";
  }
  return res - used[v];
}

int find_best(int n) {
  int pos = -1;

  while (true) {
    int opos = pos;
    int l = pos + 1;
    auto tmp = myAsk(l);
    if (!tmp[0] && !tmp[1]) {
      return l;
    }
    int r = l + maxVal(n, tmp[0] + tmp[1]) - 1;
    FOR(i, l, r) {
      if (sv[i].empty()) {
        continue;
      }

      if (sv[i] != tmp) {
        r = i - 1;
        break;
      }
    }
    
    r = max(l, r);
//    cout << tmp[0] + tmp[1] << " " << l << " " << r << "\n";

    while (l <= r) {
      int mid = (l + r) >> 1;
      auto cur = myAsk(mid);

      if (!cur[0] && !cur[1]) {
        return mid;
      }

      if (cur == tmp) {
        pos = mid;
        l = mid + 1;
      }
      else {
        r = mid - 1;
      }
    }

    used[tmp[0] + tmp[1]] += pos - opos;
  }
}

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