Submission #1180215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180215		Kanon	Counting Mushrooms (IOI20_mushrooms)	C++20	100 / 100	3 ms	632 KiB

mushrooms

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

using namespace std;

vector<int> Merge(vector<int> base, vector<int> Eval) {
  assert(Eval.size() <= base.size());
  vector<int> ret(Eval.size() + base.size());
  int id = ret.size() - 1;
  while (id >= 0) {
    if (Eval.size()) {
      ret[id--] = Eval.back();
      Eval.pop_back();
    }
    ret[id--] = base.back();
    base.pop_back();
  }
  return ret;
};

tuple<int, int, int, int> calc(vector<int> A_know, vector<int> B_know, vector<int> evaluating_tokens) {
  assert(evaluating_tokens.size());
  assert(evaluating_tokens.size() <= max(A_know.size(), B_know.size()));

  int last_token = evaluating_tokens.back();
  int last_token_value = -1;
  int total_A_zero = 0;
  int total_B_one = 0;

  if (A_know.size() >= B_know.size()) {
    int val = use_machine(Merge(A_know, evaluating_tokens));
    last_token_value = val & 1;
    total_B_one = val - (val & 1) >> 1;
    total_A_zero = evaluating_tokens.size() - 1 - total_B_one;
  } else {
    int val = use_machine(Merge(B_know, evaluating_tokens));
    last_token_value = val & 1 ^ 1;
    total_A_zero = val - (val & 1) >> 1;
    total_B_one = evaluating_tokens.size() - 1 - total_A_zero;
  }
  return make_tuple(total_A_zero, total_B_one, last_token, last_token_value);
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int total_A = 1;

pair<vector<int>, vector<int>> Exploring(vector<int> A_know, vector<int> B_know, vector<int> evaluating_tokens, int total_A_zero) {
  vector<int> A_ret;
  vector<int> B_ret;
  shuffle(evaluating_tokens.begin(), evaluating_tokens.end(), rng);
  if (total_A_zero == int(evaluating_tokens.size())) {
    A_ret = evaluating_tokens;
    return make_pair(A_ret, B_ret);
  } else if (total_A_zero == 0) {
    B_ret = evaluating_tokens;
    return make_pair(A_ret, B_ret);
  }
  int tokens = evaluating_tokens.size();
  int A_sum = total_A_zero;
  int try_tokens = tokens / 2;
  if (try_tokens & 1 && tokens & 1) try_tokens++;
  vector<int> Trying_tokens = vector<int>(evaluating_tokens.begin(), evaluating_tokens.begin() + try_tokens);
  vector<int> Left_tokens = vector<int>(evaluating_tokens.begin() + try_tokens, evaluating_tokens.end());
  auto [Trying_A_zeros, Trying_B_ones, last_token, last_token_value] = calc(A_know, B_know, Trying_tokens);
  if (last_token_value == 0) A_ret.push_back(last_token);
  else B_ret.push_back(last_token);
  Trying_tokens.pop_back();
  auto [AA, BB] = Exploring(A_know, B_know, Trying_tokens, Trying_A_zeros);
  auto [AAA, BBB] = Exploring(A_know, B_know, Left_tokens, total_A_zero - (last_token_value == 0) - Trying_A_zeros);
  for (int i : AA) A_ret.push_back(i);
  for (int i : AAA) A_ret.push_back(i);
  for (int i : BB) B_ret.push_back(i);
  for (int i : BBB) B_ret.push_back(i);
  return make_pair(A_ret, B_ret);
}

void Absorb(vector<int> &A_know, vector<int> &B_know, vector<int> evaluating_tokens) {
  assert(evaluating_tokens.size());
  auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, evaluating_tokens);
  evaluating_tokens.pop_back();
  if (last_token_value == 0) A_know.push_back(last_token);
  else B_know.push_back(last_token);
  auto [A, B] = Exploring(A_know, B_know, evaluating_tokens, total_A_zero);
  for (int i : A) A_know.push_back(i);
  for (int i : B) B_know.push_back(i);
  total_A += A.size() + (last_token_value == 0);
}

vector<int> Hidden(vector<int> r, vector<int> Move) {
  for (int &i : Move) {
    if (i < 2) continue;
    i = r[i - 2];
  }
  return Move;
}

int machine(vector<int> hidden) {
  int cur = 0;
  for (int i = 0; i < hidden.size() - 1; i++) cur += hidden[i] != hidden[i + 1];
  return cur;
}

vector<int> first_move = {2, 3, 4, 0, 1, 5, 1, 1, 6};
vector<vector<int>> result_to_next_move = {
{0, 1, 1, 1, 2, 3, 4, 5, 6},
{0, 1, 1, 1, 2, 3, 5, 4, 6},
{1, 2, 1, 3, 1, 5, 0, 6, 4},
{1, 2, 1, 6, 1, 0, 5, 3, 4},
{0, 2, 5, 1, 1, 6, 1, 4, 3},
{0, 1, 1, 1, 2, 4, 6, 5, 3},
{0, 1, 1, 1, 2, 3, 4, 5, 6}
};

vector<int> Converse(vector<int> A_know, vector<int> B_know, vector<int> ids, int A_val, int B_val, vector<int> Move) {
  assert(count(Move.begin(), Move.end(), A_val) <= A_know.size() && count(Move.begin(), Move.end(), B_val) <= B_know.size());
  for (int &i : Move) {
    if (i >= 2) i = ids[i - 2];
    else if (i == A_val) {
      i = A_know.back();
      A_know.pop_back();
    } else {
      i = B_know.back();
      B_know.pop_back();
    }
  }
  return Move;
}

vector<int> mask_to_vec(int msk, int sz) {
  vector<int> r;
  for (int i = 0; i < sz; i++) {
    r.push_back(msk >> i & 1);
  }
  return r;
}

pair<int, int> unique_value(vector<int> r) {
  assert(r.size() == 5);
  int first = machine(Hidden(r, first_move));
  vector<int> second_move = result_to_next_move[first - 1];
  int second = machine(Hidden(r, second_move));
  return make_pair(first, second);
}

vector<int> Short_explore(vector<int> A_know, vector<int> B_know, vector<int> ids) {
  int A_val, B_val;
  assert(ids.size() == 5);
  assert(max(A_know.size(), B_know.size()) >= 3 && min(A_know.size(), B_know.size()) >= 1);
  if (A_know.size() >= 3) {
    A_val = 1;
    B_val = 0;
  } else {
    B_val = 1;
    A_val = 0;
  }
  vector<int> F = Converse(A_know, B_know, ids, A_val, B_val, first_move);
  int result = use_machine(F);
  vector<int> S = result_to_next_move[result - 1];
  S = Converse(A_know, B_know, ids, A_val, B_val, S);
  int result2 = use_machine(S);
  for (int msk = 0; msk < (1 << 5); msk++) {
    vector<int> r = mask_to_vec(msk, 5);
    auto [f, s] = unique_value(r);
    if (f == result && s == result2) {
      for (int &i : r) i ^= A_val;
      return r;
    }
  }
  assert(false);
}


int skip_to_max = uniform_int_distribution<int>(95, 105)(rng);

int count_mushrooms(int n) {

  vector<int> A_know = {0};
  vector<int> B_know;
  vector<int> untouched(n - 1);
  iota(untouched.begin(), untouched.end(), 1);
  shuffle(untouched.begin(), untouched.end(), rng);
  int ptr = 0;

  if (n <= 220) {
    while (ptr < n - 1) {
      vector<int> foo = {untouched[ptr]};
      Absorb(A_know, B_know, foo);
      ptr++;
    }
    return total_A;
  }

  while (max(A_know.size(), B_know.size()) < 3 || min(A_know.size(), B_know.size()) < 1) {
    int try_tokens = min(2, int(max(A_know.size(), B_know.size())));
    vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
    ptr += try_tokens;
    Absorb(A_know, B_know, foo);
    if (A_know.size() + B_know.size() >= 2 * skip_to_max) break;
  }

  while (A_know.size() + B_know.size() < 2 * skip_to_max) {
    int try_tokens = 5;
    vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
    vector<int> unveil = Short_explore(A_know, B_know, foo);
    for (int i = 0; i < try_tokens; i++) {
      total_A += unveil[i] == 0;
      if (unveil[i] == 0) A_know.push_back(foo[i]);
      else B_know.push_back(foo[i]);
    }
    ptr += try_tokens;
  }


  while (ptr < n - 1) {
    int try_tokens = max(A_know.size(), B_know.size());
    try_tokens = min(try_tokens, n - 1 - ptr);
    vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
    ptr += try_tokens;
    auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, foo);
    total_A += total_A_zero + (last_token_value == 0);
    if (last_token_value == 0) A_know.push_back(last_token);
    else B_know.push_back(last_token);
  }
  return total_A;
}

• Subtask 1: 100 / 100