// WIP: REFACTORING
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 100;
bool swapped;
int i, count_A, count_B;
vector<int> A, B;
void get_same_two_pivots() {
while (A.size() < 2 and B.size() < 2) {
if (0 == use_machine({ 0, i })) {
A.push_back(i);
} else {
B.push_back(i);
}
i += 1;
}
}
void get_mixed_three_two_pivots() {
// TODO refactor while condition
while ( (A.size() < 3 or B.size() < 2) and
(A.size() < 2 or B.size() < 3) and
(A.size() < M and B.size() < M) ) {
if (A.size() < B.size()) {
swapped = not swapped;
swap(A, B);
}
switch (use_machine({ i, A[0], i+1, A[1] })) {
case 0:
A.insert(A.end(), { i, i+1 });
break;
case 1:
B.push_back(i);
A.push_back(i+1);
break;
case 2:
A.push_back(i);
B.push_back(i+1);
break;
default: // XXX TODO FIXME
B.insert(B.end(), { i, i+1 });
}
i += 2;
}
}
void get_same_many_pivots() { // TODO argument: limits
// TODO M is somewhat magic number, can we determine them in term of n?
while (A.size() < M && B.size() < M) {
if (A.size() < B.size()) {
swapped = not swapped;
swap(A, B);
}
int result = use_machine({ i, A[0], i+1, A[1], i+2, A[2] });
int parity = result % 2;
switch (parity) {
case 0:
A.push_back(i);
break;
case 1:
B.push_back(i);
break;
}
switch (result - parity) {
case 0:
A.insert(A.end(), { i+1, i+2 });
i += 3;
break;
case 4:
B.insert(B.end(), { i+1, i+2 });
i += 3;
break;
case 2:
switch (use_machine({ B[0], i+1, B[1], A[0], i+2, A[1], i+3, A[2], i+4 })) {
case 1:
A.insert(A.end(), { i+2, i+3, i+4 });
B.insert(B.end(), { i+1 });
break;
case 2:
A.insert(A.end(), { i+2, i+3 });
B.insert(B.end(), { i+1, i+4 });
break;
case 3:
A.insert(A.end(), { i+2, i+4 });
B.insert(B.end(), { i+1, i+3 });
break;
case 4:
A.insert(A.end(), { i+2 });
B.insert(B.end(), { i+1, i+3, i+4 });
break;
case 5:
A.insert(A.end(), { i+1, i+3, i+4 });
B.insert(B.end(), { i+2 });
break;
case 6:
A.insert(A.end(), { i+1, i+3 });
B.insert(B.end(), { i+2, i+4 });
break;
case 7:
A.insert(A.end(), { i+1, i+4 });
B.insert(B.end(), { i+2, i+3 });
break;
default: // TODO XXX FIXME PLS NO DEFAULT!!
A.insert(A.end(), { i+1 });
B.insert(B.end(), { i+2, i+3, i+4 });
}
i += 5;
}
}
}
void count_the_rest(int n) {
if (swapped) {
swapped = not swapped;
swap(A, B);
}
count_A = A.size();
count_B = B.size();
while (i < n) {
if (A.size() < B.size()) {
swapped = not swapped;
swap(A, B);
swap(count_A, count_B);
}
vector<int> x;
int L = min((int)A.size(), n-i);
for (int j=0; j<L; j++) {
x.push_back(i+j);
x.push_back(A[j]);
}
int result = use_machine(x);
int parity = result % 2;
if (parity == 0) {
A.push_back(i);
count_A += 1;
} else {
B.push_back(i);
count_B += 1;
}
count_B += result/2;
count_A += (L-1) - result/2;
i += L;
}
if (swapped) {
swapped = not swapped;
swap(A, B);
swap(count_A, count_B);
}
}
int naive(int n) {
while (i < n) {
vector<int> x;
x.push_back(0);
x.push_back(i);
int result = use_machine(x);
if (result == 0 ) {
A.push_back(i);
count_A += 1;
} else {
B.push_back(i);
count_B += 1;
}
i += 1;
}
return count_A;
}
int count_mushrooms(int n) {
swapped = false;
i = 1;
A = { 0 };
B = { };
if (n <= 226) {
return naive(n);
}
get_same_two_pivots();
get_mixed_three_two_pivots();
get_same_many_pivots();
count_the_rest(n);
return count_A;
}
