제출 #395939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395939		usachevd0	커다란 상품 (IOI17_prize)	C++17	90 / 100	109 ms	2636 KiB

prize

#include <bits/stdc++.h>
#ifndef DEBUG
  #include "prize.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) {
  return y < x ? (x = y, true) : false; 
}
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

const int maxN = 200005;

#ifdef DEBUG
  int a[maxN];
  int cnt[maxN];
  pii f[maxN];
  vector<int> ask(int i) {
    return {f[i].fi, f[i].se};
  }
#endif

pii res[maxN];
int val[maxN];
set<int> vals;

pii Ask(int i) {
  if (res[i].fi != -1) {
    return res[i];
  }
  auto a = ask(i);
  val[i] = a[0] + a[1];
  vals.insert(val[i]);
  return res[i] = {a[0], a[1]};
}

int find_best(int n) {
  memset(res, 255, sizeof res);
  memset(val, 255, sizeof val);
  vals.clear();

  #define ASK(i) Ask(i); if (!val[i]) return i

  int i = 0;
  while (i < n) {
    ASK(i);
    bool i_not_max = val[i] != *vals.rbegin();
    int vl = i;
    int vr = n;
    while (vr - vl > 1 && !i_not_max) {
      int vm = (vl + vr) >> 1;
      ASK(vm);
      if (val[vm] == val[i]) {
        if (res[i].fi == res[vm].fi) {
          vl = vm;
        } else {
          vr = vm;
        }
      } else if (val[vm] > val[i]) {
        i_not_max = true;
        break;
      } else {
        vr = vm;
      }
    }
    if (i_not_max) {
      ++i;
      continue;
    }
    ASK(vr);
    i = vr + 1;
  }
  throw;
}

#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  mt19937 rng(228);
  int n = 5;
  int C = 3;
  for (int itr = 1; ; ++itr) {
    int M = -1e9;
    int one_i = rng() % n;
    a[one_i] = 1;
    fill(cnt, cnt + C + 1, 0);
    for (int i = 0; i < n; ++i) {
      if (i != one_i) {
        a[i] = rng() % (C - 1) + 2;
      }
      chkmax(M, a[i]);
      ++cnt[a[i]];
      f[i].fi = accumulate(cnt, cnt + a[i], 0);
    }
    bool bad = false;
    for (int k = 2; k <= M; ++k) {
      if (cnt[k] <= cnt[k - 1] * (ll)cnt[k - 1]) {
        bad = true;
        break;
      }
    }
    if (bad) continue;
    fill(cnt, cnt + C + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
      ++cnt[a[i]];
      f[i].se = accumulate(cnt, cnt + a[i], 0);
    }
    int i = find_best(n);
    assert(0 <= i && i < n && a[i] == 1);
    debug(itr);
  }
  /*int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    ++cnt[a[i]];
    f[i].fi = accumulate(cnt, cnt + a[i], 0);
  }
  fill(cnt, cnt + n + 1, 0);
  for (int i = n - 1; i >= 0; --i) {
    ++cnt[a[i]];
    f[i].se = accumulate(cnt, cnt + a[i], 0);
  }
  mdebug(f, n);
  int i = find_best(n);
  debug(i);
  assert(0 <= i && i < n && a[i] == 1);*/
    
  return 0;
}
#endif

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