Submission #813346

#	Time	Username	Problem	Language	Result	Execution time	Memory
813346		erray	The Big Prize (IOI17_prize)	C++17	100 / 100	46 ms	1956 KiB

prize

#include "prize.h"
//author: erray
#include <bits/stdc++.h>

using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/debug.h"
#else
  #define debug(...) (void) 37
#endif

const int J = 9;
const int SMALL = 490;

int find_best(int N) {
  vector<int> ll(N, -1), rr(N);
  auto Pull = [&](int x) {
    if (ll[x] == -1) {
      auto g = ask(x);
      ll[x] = g[0];
      rr[x] = g[1];
    }
  };
  auto L = [&](int x) {
    Pull(x);
    return ll[x];
  };
  auto R = [&](int x) {
    Pull(x);
    return rr[x];
  };
  auto Rank = [&](int x) {
    return L(x) + R(x);
  };
  function<void(int, int)> Dfs = [&](int l, int r) {
    if (l == r) {
      Pull(l);
      return;
    }
    if (Rank(l) == Rank(r)) {
      if (L(r) == L(l)) {
        return;
      }
      int mid = (l + r) >> 1;
      Dfs(l, mid);
      Dfs(mid, r);
    } else if (Rank(l) > Rank(r)) {
      Dfs(l, r - 1);
    } else {
      Dfs(l + 1, r);
    }
  };  
  Dfs(0, N - 1);
  /*
  int c = 0; 
  while (c <= N - 1) {
    int next = min(N - 1, c + (1 << J));
    function<void(int, int)> Dfs = [&](int l, int r) {
      if (l == r) {
        Pull(l);
        return;
      }
      if (Rank(l) == Rank(r)) {
        if (L(r) == L(l)) {
          return;
        }
        int mid = (l + r) >> 1;
        Dfs(l, mid);
        Dfs(mid, r);
      } else if (Rank(l) > Rank(r)) {
        Dfs(l, r - 1);
      } else {
        Dfs(l + 1, r);
      }
    };
    Dfs(c, next);
    c = next + 1;
  }
  */
  int ans = -1;
  for (int i = 0; i < N; ++i) {
    if (ll[i] != -1 && Rank(i) == 0) {
      ans = i;
    }
  }
  debug(ans);
  return ans;
}

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