Submission #613935

#	Time	Username	Problem	Language	Result	Execution time	Memory
613935		Mamedov	The Big Prize (IOI17_prize)	C++17	100 / 100	77 ms	12144 KiB

prize

#pragma GCC optimize ("O3")
#include "prize.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int up = 2e5 + 5;
int okay = 0;
vi cnt[up];

vi ASK(int i) {
  if (cnt[i][0] != oo) return cnt[i];
  else return ask(i);
}

void solve(int l, int r, int subL, int subR) {
  if (l <= r) {
    int mid = (l + r) >> 1;
    vi a = ASK(mid);
    if (a[0] + a[1] < okay) { /// not last type
      int lmid = mid - 1, rmid = mid + 1;
      cnt[mid] = a;
      while (lmid >= l) {
        a = ASK(lmid);
        if (a[0] + a[1] < okay) {
          cnt[lmid] = a;
          --lmid;
        } else {
          break;
        }
      }
      if (a[0] - subL > 0 && lmid > l) {
        solve(l, lmid - 1, subL, a[1]);
      }
      while (rmid <= r) {
        a = ASK(rmid);
        if (a[0] + a[1] < okay) {
          cnt[rmid] = a;
          ++rmid;
        } else {
          break;
        }
      }
      if (a[1] - subR > 0 && rmid < r) {
        solve(rmid + 1, r, a[0], subR);
      }
    } else { /// last type
      if (a[0] - subL > 0) {
        solve(l, mid - 1, subL, a[1]);
      }
      if (a[1] - subR > 0) {
        solve(mid + 1, r, a[0], subR);
      }
    }
  }
}
int find_best(int n) {
  vi p(n);
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    cnt[i] = {oo, oo};
  }
  shuffle(all(p), rng);
  for (int i = 0; i < n && i < 473; ++i) {  /// type_cnt[1, 4, 21, 446, last] 1 + 4 + 21 + 446 = 472
    cnt[p[i]] = ASK(p[i]);
    okay = max(okay, cnt[p[i]][0] + cnt[p[i]][1]);
    if (okay > 26) break;   /// 1 + 4 + 21 = 26
  }
  solve(0, n - 1, 0, 0);
  for (int i = 0; i < n; ++i) {
    if (cnt[i][0] + cnt[i][1] == 0) return i;
  }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:77:9: warning: control reaches end of non-void function [-Wreturn-type]
   77 |   vi p(n);
      |         ^

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