Submission #956850

#	Time	Username	Problem	Language	Result	Execution time	Memory
956850		Numberz	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	5 ms	876 KiB

mushrooms

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

//a contains the a and b, but easy to swap
vector<int> a[2], ve;
//res = answer, 
int res, x, c, k, r;

void update() {
  if (a[0].size() < a[1].size()) {
    res = r - res;
    swap(a[0], a[1]);
    c ^= 1;
  }
}

int count_mushrooms(int n) {
  //if n is small, we dont need to go through all this trouble, just check the all directly
  if (n <= 227) {
    for (int i = 1; i < n; i++) {
      res += 1 - use_machine({0, i});
    }
    return res + 1;
  }

  a[0] = {0};
  //clever way to not FALLUNTERSCHEID them
  for (int i = 1; i < 3; i++) {
    int x = use_machine({0, i});
    a[x].push_back(i);
  }
  update();
  //get at least 5 items
  x = use_machine({3, a[0][0], 4, a[0][1]});
  a[x&1].push_back(3);
  a[x/2&1].push_back(4);
  update();


  //in the first phase we collect as much explicit using this nice method
  //using 2 queries, we can determine 5 items
  //we find first explicit, then we know if the others are the same or dif
  //if same-> we know what, else we know they are different
  //in the last case we have limited number of possiblities, so just check all of them
  //with this nice trick
  for (int i = 5; max(a[0].size(), a[1].size()) < 100;) {
    x = use_machine({i, a[0][0], i+1, a[0][1], i+2, a[0][2]});
    a[x&1].push_back(i);
    if (!(x/2 % 2)) {
      a[x/4].push_back(i+1);
      a[x/4].push_back(i+2);
      i+=3;
    } else if (a[1].size() < 2) {
      x = use_machine({a[0][0], i+1});
      a[x].push_back(i+1);
      a[x^1].push_back(i+2);
      i+=3;
    } else {
      x = use_machine({i+4, a[0][0], i+3, a[0][1], i+2, a[0][2], a[1][0], i+1, a[1][1]})-1;
      a[x&1].push_back(i+4);
      a[x/2&1].push_back(i+3);
      a[x/4].push_back(i+2);
      a[x/4^1].push_back(i+1);
      i += 5;
    }
  }
  update();
  //now phase 2
  res = a[1].size();
  for (int i = a[0].size() + a[1].size(); i < n; i = r) {
    ve.clear();//(int)
    r = min(i+(int)a[0].size(), n);
    for (int j = i; j < r; j++) {
      ve.push_back(j);
      ve.push_back(a[0][j-i]);
    }
    x = use_machine(ve);
    res += (x+1)/2;
    a[x&1].push_back(i);
    update();
  }

  return (c ? res : n - res);
  
}

• Subtask 1: 100 / 100