// WIP: REFACTORING
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 100;
vector<int> A, B;
int count_A, count_B, i;
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;
}
// XXX defer this to very later (part 4);
count_A = A.size();
count_B = B.size();
}
void get_mixed_three_two_pivots() {
// TODO refactor while condition
while ( (count_A < 3 or count_B < 2) and
(count_A < 2 or count_B < 3) and
count_A < M and count_B < M ) {
bool swapped = false;
if (count_A < count_B) {
swapped = true;
swap(A, B);
swap(count_A, count_B);
}
switch (use_machine({ i, A[0], i+1, A[1] })) {
case 0:
A.insert(A.end(), { i, i+1 });
count_A += 2;
break;
case 1:
B.push_back(i);
A.push_back(i+1);
count_A++;
count_B++;
break;
case 2:
A.push_back(i);
B.push_back(i+1);
count_A++;
count_B++;
break;
default:
B.insert(B.end(), { i, i+1 });
count_B += 2;
}
if (swapped) {
swap(A, B);
swap(count_A, count_B);
}
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 (count_A < M && count_B < M) {
bool swapped = false;
if (count_A < count_B) {
swapped = true;
swap(A, B);
swap(count_A, count_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);
count_A++;
break;
case 1:
B.push_back(i);
count_B++;
break;
}
switch (result - parity) {
case 0:
A.insert(A.end(), { i+1, i+2 });
count_A += 2;
i += 3;
break;
case 4:
B.insert(B.end(), { i+1, i+2 });
count_B += 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 });
//B.push_back(i+1);
//A.push_back(i+2);
//A.push_back(i+3);
//A.push_back(i+4);
count_A += 3;
count_B += 1;
break;
case 2:
A.insert(A.end(), { i+2, i+3 });
B.insert(B.end(), { i+1, i+4 });
//B.push_back(i+1);
//A.push_back(i+2);
//A.push_back(i+3);
//B.push_back(i+4);
count_A += 2;
count_B += 2;
break;
case 3:
A.insert(A.end(), { i+2, i+4 });
B.insert(B.end(), { i+1, i+3 });
//B.push_back(i+1);
//A.push_back(i+2);
//B.push_back(i+3);
//A.push_back(i+4);
// TODO DESIGN: assign(offset=1, arr={ B, A, B, A });
count_A += 2;
count_B += 2;
break;
case 4:
A.insert(A.end(), { i+2 });
B.insert(B.end(), { i+1, i+3, i+4 });
//B.push_back(i+1);
//A.push_back(i+2);
//B.push_back(i+3);
//B.push_back(i+4);
count_A += 1;
count_B += 3;
break;
case 5:
A.insert(A.end(), { i+1, i+3, i+4 });
B.insert(B.end(), { i+2 });
//A.push_back(i+1);
//B.push_back(i+2);
//A.push_back(i+3);
//A.push_back(i+4);
count_A += 3;
count_B += 1;
break;
case 6:
A.insert(A.end(), { i+1, i+3 });
B.insert(B.end(), { i+2, i+4 });
//A.push_back(i+1);
//B.push_back(i+2);
//A.push_back(i+3);
//B.push_back(i+4);
count_A += 2;
count_B += 2;
break;
case 7:
A.insert(A.end(), { i+1, i+4 });
B.insert(B.end(), { i+2, i+3 });
//A.push_back(i+1);
//B.push_back(i+2);
//B.push_back(i+3);
//A.push_back(i+4);
count_A += 2;
count_B += 2;
break;
default: // TODO XXX FIXME PLS NO DEFAULT!!
A.insert(A.end(), { i+1 });
B.insert(B.end(), { i+2, i+3, i+4 });
//A.push_back(i+1);
//B.push_back(i+2);
//B.push_back(i+3);
//B.push_back(i+4);
count_A += 1;
count_B += 3;
}
i += 5;
}
if (swapped) {
swap(A, B);
swap(count_A, count_B);
}
}
}
void count_the_rest(int n) {
while (i < n) {
bool swapped = false;
if (A.size() < B.size()) {
swapped = true;
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);
if (result%2 == 0) {
A.push_back(i);
count_A++;
} else {
B.push_back(i);
count_B++;
}
count_B += result/2;
count_A += (L-1) - result/2;
if (swapped) {
swap(A, B);
swap(count_A, count_B);
}
i += L;
}
}
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++;
} else {
B.push_back(i);
count_B++;
}
i++;
}
return count_A;
}
int count_mushrooms(int n) {
A = { 0 };
B = { };
count_A = 1;
count_B = 0;
i = 1;
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;
}
