Submission #1204855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204855		bangan	Counting Mushrooms (IOI20_mushrooms)	C++20	91.13 / 100	3 ms	520 KiB

mushrooms

#include "mushrooms.h"

using namespace std;

const int A = 227;

int count_mushrooms(int n) {
  if (n <= A) {
    int ans = 1;
    for (int i = 1; i < n; i++) {
      vector<int> g = {0, i};
      ans += !use_machine(g);
    }
    return ans;
  }

  vector<int> st(A, 0);
  st[1] = use_machine({0, 1});
  st[2] = use_machine({0, 2});
  int p = 0;
  if (st[1] == st[2] && st[1] == 1) {
    p = 0;
  } else if (st[0] == st[1]) {
    p = 1;
  }
  else {
    p = 2;
  }
  
  for (int i = 3; i < A; i += 2) {
    int res = 0;
    if (p) {
      res = use_machine({0, i, p, i + 1});
      if (res == 0) {
        st[i] = st[i + 1] = 0;
      }
      else if (res == 1) {
        st[i + 1] = 1;
      }
      else if (res == 2) {
        st[i] = 1;
      }
      else {
        st[i] = st[i + 1] = 1;
      }
    } 
    else {
      res = use_machine({1, i, 2, i + 1});
      if (res == 0) {
        st[i] = st[i + 1] = 1;
      }
      else if (res == 1) {
        st[i] = 1;
      }
      else if (res == 2) {
        st[i + 1] = 1;
      }
      else {
        st[i] = st[i + 1] = 0;
      }
    }
  }

  int cnt = 0, ans = 0;
  for (int i = 0; i < A; i++) {
    ans += !st[i];
    cnt += st[i];
  }

  vector<int> g[2];
  int t = (cnt > A / 2);
  for (int i = 0; i < A; i++) {
    if (st[i] == t) {
      g[0].push_back(i);
    } else {
      g[1].push_back(i);
    }
  }

  vector<int> rem;
  for (int i = A; i < n; i++) {
    rem.push_back(i);
  }

  while (!rem.empty()) {
    if (g[0].size() < g[1].size()) {
      t = 1 - t;
      swap(g[0], g[1]);
    }
    
    vector<int> x;
    while (!rem.empty() && !g[0].empty()) {
      x.push_back(rem.back());
      x.push_back(g[0].back());
    
      rem.pop_back();
      g[0].pop_back();
    }

    int res = use_machine(x);
    if (res % 2 == 1) {
      res++;
      g[1].push_back(x[0]);
    }
    else {
      g[0].push_back(x[0]);
    }
    res /= 2;

    if (t == 1) {
      ans += res;
    } else {
      int sz = (int)x.size();
      sz /= 2;
      ans += sz - res;
    }

    while (!x.empty()) {
      g[0].push_back(x.back());
      x.pop_back(); x.pop_back();
    }
  }

  return ans;
}

• Subtask 1: 91.129 / 100