Submission #299607

#	Time	Username	Problem	Language	Result	Execution time	Memory
299607		kevlee	The Big Prize (IOI17_prize)	C++17	100 / 100	74 ms	5396 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define SQ 450
vi mem[200005];
int prize = -1, maxx;
void solve(int l, int r, int aim) {
  if (l > r || aim <= 0 || prize != -1) return;
  //cout << l << ' ' << r << ' ' << aim << endl;
  int mid = (l + r) >> 1;
  vi res = mem[mid];
  if (res.empty()) {
    mem[mid] = ask(mid);
    res = mem[mid];
  }
  //cout << res[0] << "  " << res[1] << endl;
  if (res[0] + res[1] == 0) {
    prize = mid;
    //cout << "Found up there" << endl;
    return;
  }
  if (res[0] + res[1] == maxx) {
    //cout << "hello " <<mem[l-1][0] << endl;
    solve(l, mid - 1, res[0] - mem[l-1][0]);
    solve(mid + 1, r, aim - (res[0] - mem[l-1][0]));
  } else {
    int pointer = mid;
    while (pointer < r) {
      pointer++;
      res = mem[pointer];
      if (res.empty()) {
        mem[pointer] = ask(pointer);
        res = mem[pointer];
      }
      if (res[0] + res[1] == 0) {
        prize = pointer;
        //cout << "Found up there" << endl;
        return;
      }
      if (res[0] + res[1] == maxx) {
        solve(l, mid - 1, res[0] - mem[l-1][0] - (pointer - mid));
        solve(pointer + 1, r, aim - (res[0] - mem[l-1][0]));
        return;
      }
    }
    solve(l, mid - 1, aim - (r - mid + 1));
  }
}
int find_best(int n) {
  if (n <= 5000) {
    FOR(i, 0, n-1) {
      vi tmp = ask(i);
      if (tmp[0] + tmp[1] == 0) return i;
    }
  }
  //----
  int cnt = 0;
  for (int i = 0; i < n; i += 500) {
    cnt++;
    mem[i] = ask(i);
    if (mem[i][0] + mem[i][1] == 0) return i; 
    maxx = max(maxx, mem[i][0] + mem[i][1]);
  }
  FOR(i, 0, n-1) {
    if (i % 500 == 0) continue;
    if (cnt >= 500) break;
    cnt++;
    mem[i] = ask(i);
    if (mem[i][0] + mem[i][1] == 0) return i; 
    maxx = max(maxx, mem[i][0] + mem[i][1]);
  }
  vi seg;
  for (int i = 0; i < n; ) {
    while (i < n) {
      if (mem[i].empty()) {
        mem[i] = ask(i);
        if (mem[i][0] + mem[i][1] == 0) return i;
      }
      if (mem[i][0] + mem[i][1] == maxx) {
        break;
      }
      i++;
    }
    if (i < n && mem[i][0] + mem[i][1] == maxx) seg.pb(i);
    i++;
    while (i < n) {
      if (i % 500 == 0) break;
      i++;
    }
  }
  int last = -1, sum = 0;
  for (int pos: seg) {
    ///cout << pos << ": " << mem[pos][0] - sum << endl;
    solve(last + 1, pos - 1, mem[pos][0] - sum);
    sum = mem[pos][0];
    last = pos;
  }
  assert(last != -1);
  solve(last + 1, n - 1, mem[last][1]);
	return prize;
}

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