#include "mushrooms.h"
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
#define query use_machine
#define pb push_back
using namespace std;
int count_mushrooms(int n) {
mt19937 rng(time(0));
const int lim = 105;
int pos, cnt, tmp;
vector<int> a, b, v, q, ar, c, d;
for (int i = 1; i < n; i++) ar.pb(i);
for (int i = 1; i <= 10; i++) shuffle(ar.begin(),ar.end(),rng);
ar.pb(0);
reverse(ar.begin(),ar.end());
if (n == 2) return 2-query({ar[0],ar[1]});
a.pb(ar[0]);
for (int i = 1; i <= 2; i++) {
//if ((a.size() >= 2) || (b.size() >= 2)) break;
pos = i+1;
if (query({ar[0],ar[i]}) == 0) a.pb(ar[i]);
else b.pb(ar[i]);
}
while ((a.size() < lim) && (b.size() < lim)) {
if ((pos+2 < n) && (a.size() >= 2) && (b.size() >= 2)) {
tmp = query({a[0],ar[pos],a[1],b[0],ar[pos+1],b[1],ar[pos+2]});
if (tmp%2 == 0) a.pb(ar[pos+2]);
else b.pb(ar[pos+2]);
if ((tmp-1)/2 == 0) a.pb(ar[pos]),b.pb(ar[pos+1]);
else if ((tmp-1)/2 == 2) a.pb(ar[pos+1]),b.pb(ar[pos]);
else {
c.pb(ar[pos]); c.pb(ar[pos+1]);
if (c.size() == 6) {
tmp = query({a[0],c[0],c[1],a[1],b[0],c[2],c[3],b[1],c[4],c[5]});
if (tmp%2 == 0) a.pb(c[4]), a.pb(c[5]);
else b.pb(c[4]), b.pb(c[5]);
if ((tmp-1)/2 == 0) a.pb(c[0]), a.pb(c[1]), b.pb(c[2]), b.pb(c[3]);
else if ((tmp-1)/2 == 2) a.pb(c[2]), a.pb(c[3]), b.pb(c[0]), b.pb(c[1]);
else {
d.pb(c[0]); d.pb(c[1]); d.pb(c[2]); d.pb(c[3]);
if (d.size() == 8) {
tmp = query({a[0],d[0],d[1],d[2],d[3],a[1],d[4],d[5],d[6],d[7]});
if (tmp == 0) a.pb(d[0]), a.pb(d[1]), a.pb(d[2]), a.pb(d[3]), a.pb(d[4]), a.pb(d[5]), a.pb(d[6]), a.pb(d[7]);
else if (tmp == 1) a.pb(d[0]), a.pb(d[1]), a.pb(d[2]), a.pb(d[3]), b.pb(d[4]), b.pb(d[5]), b.pb(d[6]), b.pb(d[7]);
else if (tmp == 2) b.pb(d[0]), b.pb(d[1]), b.pb(d[2]), b.pb(d[3]), a.pb(d[4]), a.pb(d[5]), a.pb(d[6]), a.pb(d[7]);
else b.pb(d[0]), b.pb(d[1]), b.pb(d[2]), b.pb(d[3]), b.pb(d[4]), b.pb(d[5]), b.pb(d[6]), b.pb(d[7]);
d.clear();
}
}
c.clear();
}
}
pos += 3;
} else if (pos+1 < n) {
if (a.size() >= 2) {
tmp = query({a[0],ar[pos],a[1],ar[pos+1]});
if (tmp == 0) a.pb(ar[pos]), a.pb(ar[pos+1]);
else if (tmp == 1) a.pb(ar[pos]), b.pb(ar[pos+1]);
else if (tmp == 2) b.pb(ar[pos]), a.pb(ar[pos+1]);
else b.pb(ar[pos]), b.pb(ar[pos+1]);
} else {
tmp = query({b[0],ar[pos],b[1],ar[pos+1]});
if (tmp == 0) b.pb(ar[pos]), b.pb(ar[pos+1]);
else if (tmp == 1) b.pb(ar[pos]), a.pb(ar[pos+1]);
else if (tmp == 2) a.pb(ar[pos]), b.pb(ar[pos+1]);
else a.pb(ar[pos]), a.pb(ar[pos+1]);
}
pos += 2;
} else break;
}
if (c.size() == 2) {
tmp = query({a[0],c[0],a[1],c[1]});
if (tmp == 0) a.pb(c[0]), a.pb(c[1]);
else if (tmp == 1) a.pb(c[0]), b.pb(c[1]);
else if (tmp == 2) b.pb(c[0]), a.pb(c[1]);
else b.pb(c[0]), b.pb(c[1]);
}
if (c.size() == 4) {
tmp = query({a[0],c[0],c[1],a[1],c[2],c[3]});
if (tmp == 0) a.push_back(c[0]), a.push_back(c[1]), a.push_back(c[2]), a.push_back(c[3]);
else if (tmp == 1) a.push_back(c[0]), a.push_back(c[1]), b.push_back(c[2]), b.push_back(c[3]);
else if (tmp == 2) b.push_back(c[0]), b.push_back(c[1]), a.push_back(c[2]), a.push_back(c[3]);
else b.push_back(c[0]), b.push_back(c[1]), b.push_back(c[2]), b.push_back(c[3]);
}
if (d.size()) {
tmp = query({a[0],d[0],d[1],d[2],d[3]});
if (tmp == 0) a.pb(d[0]), a.pb(d[1]), a.pb(d[2]), a.pb(d[3]);
else b.pb(d[0]), b.pb(d[1]), b.pb(d[2]), b.pb(d[3]);
}
cnt = a.size();
for (pos; pos < n; pos++) {
v.pb(ar[pos]);
if (v.size() == max(a.size(),b.size())) {
if (a.size() >= b.size()) {
q.clear();
for (int i = 0; i < v.size(); i++) {
q.pb(a[i]);
q.pb(v[i]);
}
tmp = query(q);
cnt += a.size()-(tmp+1)/2;
if (tmp%2) b.pb(ar[pos]);
else a.pb(ar[pos]);
} else {
q.clear();
for (int i = 0; i < v.size(); i++) {
q.pb(b[i]);
q.pb(v[i]);
}
tmp = query(q);
cnt += (tmp+1)/2;
if (tmp%2) a.pb(ar[pos]);
else b.pb(ar[pos]);
}
v.clear();
}
}
if (v.size()) {
if (a.size() >= b.size()) {
q.clear();
for (int i = 0; i < v.size(); i++) {
q.pb(a[i]);
q.pb(v[i]);
}
tmp = query(q);
cnt += v.size()-(tmp+1)/2;
if (tmp%2) b.pb(ar[pos]);
else a.pb(ar[pos]);
} else {
q.clear();
for (int i = 0; i < v.size(); i++) {
q.pb(b[i]);
q.pb(v[i]);
}
tmp = query(q);
cnt += (tmp+1)/2;
if (tmp%2) a.pb(ar[pos]);
else b.pb(ar[pos]);
}
}
return cnt;
}
