Submission #566304

#	Time	Username	Problem	Language	Result	Execution time	Memory
566304		lorenzoferrari	The Big Prize (IOI17_prize)	C++17	20 / 100	95 ms	1248 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

int answer = -1;
map<int, array<int, 2>> memo;
map<int, set<int>> found;

array<int, 2> askme(int i) {
  array<int, 2> ans;
  if (memo.find(i) != memo.end()) {
    ans[0] = memo[i][0];
    ans[1] = memo[i][1];
  } else {
    auto v = ask(i);
    ans[0] = v[0];
    ans[1] = v[1];
  }
  memo[i] = {ans[0], ans[1]};
  found[ans[0] + ans[1]].insert(i);
  if (ans[0] + ans[1] == 0) answer = i;
  return ans;
}
int count(int i) {
  return askme(i)[0] + askme(i)[1];
}
bool isanswer(int i) {
  return count(i) == 0;
}

void findall(int l, int r) {
  // assume t[l] = t[r] = v
  int cnt = askme(r)[0] - askme(l)[0];
  if (cnt <= 0) return;
  if (answer != -1) return;
  int m = (l + r) / 2;
  int lm = m, rm = m;
  while (count(lm) != count(l)) {
    if (answer != -1) return;
    --lm;
  }
  while (count(rm) != count(l)) {
    if (answer != -1) return;
    ++rm;
  }
  findall(l, lm);
  findall(rm, r);
}

int find_best(int n) {
  srand(time(NULL));
  int mx_cnt = 0;
  for (int i = 0; i < 4; ++i) mx_cnt = max(mx_cnt, count(rand() % n));
  int l = 0; while (count(l) != mx_cnt) ++l;
  int r = n-1; while (count(r) != mx_cnt) --r;
  findall(l, r);
  return answer;
}

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