제출 #316119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316119		MrDomino	The Big Prize (IOI17_prize)	C++14	0 / 100	104 ms	6256 KiB

prize

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

using namespace std;

mt19937 rng((long long) (new char));
const int N = 200000 + 7;
vector<int> ret[N];
int sol = -1;

vector<int> get(int i) {
  if (ret[i].empty()) {
    ret[i] = ask(i);
    if (ret[i][0] == 0 && ret[i][1] == 0) {
      sol = i;
    }
  }
  return ret[i];
}

void after(int n, int pos) {
  int cnt = 0, go = pos + 1;
  while (go < n) {
    int lo = go, hi = n - 1, id = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (get(mid)[0] + get(mid)[1] != get(pos)[0] + get(pos)[1]) {
        if (get(mid)[0] == get(pos)[0] + cnt) {
          id = mid;
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      } else {
        id = mid;
        hi = mid - 1;
      }
    }
    if (id == -1) {
      break;
    }
    if (sol != -1) {
      return;
    }
    cnt++;
    go = id + 1;
  }
}

void before(int n, int pos) {
  int cnt = 0, go = pos - 1;
  while (go >= 0) {
    int lo = 0, hi = go, id = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (get(mid)[0] + get(mid)[1] != get(pos)[0] + get(pos)[1]) {
        if (get(mid)[1] == get(pos)[1] + cnt) {
          lo = mid + 1;
          id = mid;
        } else {
          hi = mid - 1;
        }
      } else {
        id = mid;
        lo = mid + 1;
      }
    }
    if (id == -1) {
      break;
    }
    if (sol != -1) {
      return;
    }
    cnt++;
    go = id - 1;
  }
}

int find_best(int n) {
  vector<int> ord;
  for (int i = 0; i < n; i++) {
    ord.push_back(i);
  }
  shuffle(ord.begin(), ord.end(), rng);
  while ((int) ord.size() > 500) {
    ord.pop_back();
  }
  int big = 0, pos = -1;
  for (auto &i : ord) {
    big = max(big, get(i)[0] + get(i)[1]);
  }
  for (auto &i : ord) {
    if (big == get(i)[0] + get(i)[1]) {
      pos = i;
    }
  }
  assert(pos != -1);
  if (sol != -1) {
    return sol;
  }
  after(n, pos);
  if (sol != -1) {
    return sol;
  }
  before(n, pos);
  assert(sol != -1);
  return sol;
}

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