Submission #311725

#	Time	Username	Problem	Language	Result	Execution time	Memory
311725		eriksuenderhauf	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	579 ms	65912 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
int dp[255][255][255];

int go(int known_a, int known_b, int qcnt);

pair<int,int> max_val(int known_a, int known_b, int qcnt) {
  int v = 0, operation = 2;
  // A.A.(...)
  // B.B.(...)
  for (int i : {2, known_a}) {
    if (i > known_a)
      continue;
    int opt = inf;
    for (int b = 0; b < 2 && opt > v; b++) {
      if (i == 2) {
        for (int a = 0; a < 2 && opt > v; a++)
          opt = min(opt, i + go(known_a + (b ^ 1) + a, known_b + b + (a ^ 1), qcnt - 1));
      } else {
        opt = min(opt, i + go(known_a + (b ^ 1), known_b + b, qcnt - 1));
      }
    }
    if (opt > v) {
      v = opt;
      operation = i == 2 ? 1 : 2;
    }
  }

  int ok = 1;
  // 000001111100
  if (qcnt > 3) {
    int cnt = 12, qry = 4;
    if (known_a >= 7 && known_b >= 5) {
      int opt = inf;
      for (int a = 0; a <= cnt && opt > v; a++) {
        if (qcnt > qry && cnt + known_b <= known_a && a != 0)
          break;
        int b = cnt - a;
        opt = min(opt, cnt + go(known_a + a, known_b + b, qcnt - qry));
      }
      if (opt > v) {
        v = opt;
        operation = 3;
      }
      ok = 0;
    }
  }
  // 00011
  if (qcnt > 1) {
    int cnt = 5, qry = 2;
    if (known_a >= 3 && known_b >= 2) {
      int opt = inf;
      for (int a = 0; a <= cnt; a++) {
        if (qcnt > qry && cnt + known_b <= known_a && a != 0)
          break;
        int b = cnt - a;
        opt = min(opt, cnt + go(known_a + a, known_b + b, qcnt - qry));
      }
      if (opt > v) {
        v = opt;
        operation = 4;
      }
    }
  }
  // 000
  if (qcnt > 1) {
    int cnt = 3, qry = 2;
    if (known_a >= 3 && known_b >= 0) {
      int opt = inf;
      for (int a = 0; a <= cnt; a++) {
        if (qcnt > qry && cnt + known_b <= known_a && a != 0)
          break;
        int b = cnt - a;
        opt = min(opt, cnt + go(known_a + a, known_b + b, qcnt - qry));
      }
      if (opt > v) {
        v = opt;
        operation = 5;
      }
    }
  }
  return make_pair(v, operation);
}

int go(int known_a, int known_b, int qcnt) {
  if (known_b > known_a)
    swap(known_a, known_b);
  if (qcnt == 0)
    return 0;
  if (known_a > 250)
    return -inf;
  if (~dp[known_a][known_b][qcnt])
    return dp[known_a][known_b][qcnt];
  int v = max_val(known_a, known_b, qcnt).first;
  return dp[known_a][known_b][qcnt] = v;
}

vector<int> ind_a, ind_b;
int cnt_a = 0, cnt_b = 0;

void flip(int fl) {
  if (fl) {
    swap(ind_a, ind_b);
    swap(cnt_a, cnt_b);
  }
}

void askA(vector<int>& x) {
  int len = int(x.size());
  assert(int(ind_a.size()) >= len);
  vector<int> cur;
  for (int i = 0; i < len; i++)
    cur.push_back(ind_a[i]), cur.push_back(x[i]);
  int ret = use_machine(cur);
  if (ret & 1) {
    ind_b.push_back(x.back());
    cnt_b++, ret--, len--;
  } else {
    ind_a.push_back(x.back());
    cnt_a++, len--;
  }
  cnt_b += ret / 2;
  cnt_a += len - (ret / 2);
  if (ret == 0) {
    for (int i = 0; i < len; i++)
      ind_a.push_back(x[i]);
  } else if (ret == len * 2) {
    for (int i = 0; i < len; i++)
      ind_b.push_back(x[i]);
  }
}

struct op3 {
  static const int qcnt = 4, len = 12;
  inline static vector<int> ord[qcnt] = {
    {8, 0, 9, 10, 7, 11, 5, 1, 6, 4, 2, 3},
    {3, 8, 4, 2, 1, 11, 5, 10, 6, 0, 9, 7},
    {5, 7, 10, 1, 9, 3, 8, 6, 2, 11, 4, 0},
    {2, 3, 11, 4, 6, 1, 9, 8, 7, 0, 5, 10}
  };
  inline static vector<int> msk = {0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0};
  inline static map<array<int,qcnt>,int> rev;
};
struct op4 {
  static const int qcnt = 2, len = 5;
  inline static vector<int> ord[qcnt] = {
    {2, 3, 1, 0, 4},
    {1, 2, 0, 4, 3}
  };
  inline static vector<int> msk = {1, 1, 0, 0, 0};
  inline static map<array<int,qcnt>,int> rev;
};
struct op5 {
  static const int qcnt = 2, len = 3;
  inline static vector<int> ord[qcnt] = {
    {0, 1, 2},
    {1, 2, 0}
  };
  inline static vector<int> msk = {0, 0, 0};
  inline static map<array<int,qcnt>,int> rev;
};

template<class op> void ask(int mx_unused, int n, int& qcnt) {
  vector<int> x;
  for (int i = 0; i < op::len && mx_unused + i < n; i++)
    x.push_back(mx_unused + i);
  if (int(x.size()) != op::len) {
    askA(x);
    qcnt--;
    return;
  }
  assert(int(x.size()) == op::len);
  int fl = int(ind_a.size()) < int(ind_b.size());
  flip(fl);
  array<int,op::qcnt> arr;
  for (int i = 0; i < op::qcnt; i++) {
    vector<int> x_ord;
    for (int j = 0, ja = 0, jb = 0; j < op::len; j++) {
      x_ord.push_back(op::msk[j] == 0 ? ind_a[ja++] : ind_b[jb++]);
      x_ord.push_back(x[op::ord[i][j]]);
    }
    arr[i] = use_machine(x_ord);
  }
  int ans = op::rev[arr];
  cnt_b += __builtin_popcount(ans);
  cnt_a += op::len - __builtin_popcount(ans);
  for (int i = 0; i < op::len; i++)
    if ((ans >> i) & 1)
      ind_b.push_back(x[i]);
    else
      ind_a.push_back(x[i]);
  flip(fl);
  qcnt -= op::qcnt;
}

template<class op> void upd() {
  auto eval = [&](vector<int>& a, vector<int>& b) {
    assert(int(a.size()) == int(b.size()));
    int r = 0;
    for (int i = 0, j = int(a.size()); i < j; i++)
      r += int(a[i] != b[i]) + int(i + 1 != j ? b[i] != a[i+1] : 0);
    return r;
  };
  for (int msk = 0; msk < (1 << op::len); msk++) {
    array<int,op::qcnt> arr;
    for (int it = 0; it < op::qcnt; it++) {
      vector<int> ord;
      for (int j = 0; j < op::len; j++)
        ord.push_back((msk >> op::ord[it][j]) & 1);
      arr[it] = eval(op::msk, ord);
    }
    op::rev[arr] = msk;
  }
}

void build() {
  upd<op3>();
  upd<op4>();
  upd<op5>();
}

void solve(int known_a, int known_b, int qcnt, int n) {
  assert(qcnt >= 0);
  int mx_unused = cnt_a + cnt_b;
  if (mx_unused >= n)
    return;
  int fl = int(known_a < known_b);
  if (fl)
    swap(known_a, known_b);
  flip(fl);
  int operation = max_val(known_a, known_b, qcnt).second;
  vector<int> x;
  switch (operation) {
    case 1: {
      for (int i = 0; i < 2 && mx_unused + i < n; i++)
        x.push_back(mx_unused + i);
      askA(x);
      qcnt--;
      break;
    }
    case 2: {
      for (int i = 0; i < known_a && mx_unused + i < n; i++)
        x.push_back(mx_unused + i);
      askA(x);
      qcnt--;
      break;
    }
    case 3: {
      ask<op3>(mx_unused, n, qcnt);
      break;
    }
    case 4: {
      ask<op4>(mx_unused, n, qcnt);
      break;
    }
    case 5: {
      ask<op5>(mx_unused, n, qcnt);
      break;
    }
  }
  flip(fl);
  solve(int(ind_a.size()), int(ind_b.size()), qcnt, n);
}

int count_mushrooms(int n) {
  memset(dp, -1, sizeof dp);
  go(1, 0, 213);
  build();
  ind_a.push_back(0);
  cnt_a = 1;
  solve(1, 0, 213, n);
  return cnt_a;
}

Compilation message (stderr)

mushrooms.cpp: In function 'std::pair<int, int> max_val(int, int, int)':
mushrooms.cpp:31:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   31 |   int ok = 1;
      |       ^~

• Subtask 1: 100 / 100