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