Submission #566466

#	Time	Username	Problem	Language	Result	Execution time	Memory
566466		lorenzoferrari	The Big Prize (IOI17_prize)	C++17	100 / 100	63 ms	736 KiB

prize

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

int mx_cnt;
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 makes_sense(int l, int r) {
  for (auto& ss : found) {
    auto& s = ss.second;
    auto il = s.lower_bound(l);
    auto ir = s.lower_bound(r);
    if (il == s.begin()) continue;
    if (ir == s.end()) continue;
    il = prev(il);
    if (askme(*ir)[0] - askme(*il)[0] <= 0) return false;
  }
  return true;
}

queue<array<int, 2>> qs;

void findall(int l, int r) {
  while (l <= r && count(l) != count(r)) {
    if (answer != -1) return;
    if (count(l) > count(r)) {
      --r;
    } else {
      ++l;
    }
  }
  // for (; count(l) != mx_cnt; ++l) if (answer != -1) return;
  // for (; count(r) != mx_cnt; --r) if (answer != -1) return;
  if (!makes_sense(l, r)) return;
  if (l >= r) return;
  int cnt = askme(r)[0] - askme(l)[0];
  if (cnt <= 0) return;
  if (answer != -1) return;
  int m = (l + r) / 2;
  qs.push({l, m});
  qs.push({m, r});
}

int find_best(int n) {
  srand(time(NULL));
  qs.push({0, n-1});
  while (!qs.empty()) {
    auto [l, r] = qs.front();
    qs.pop();
    findall(l, r);
  }
  assert(answer != -1);
  return answer;
}

#ifdef LORENZO
int main() {
  cout << "insert n: "; fflush(stdout);
  int n; cin >> n;
  cout << "answer: " << find_best(n) << endl;
}
#endif

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