#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int X=100; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int count_mushrooms(int n){ vector<int> ord; for (int i=1; i<n; ++i)ord.pb(i); vector<vector<int> > vect(2); vect[0].pb(0); if (n<=227){ int res=1; for (int i=1; i<n; ++i)res+=!use_machine({0, i}); return res; } while (max(vect[0].size(), vect[1].size())<2){ if (use_machine({0, ord.back()}))vect[1].pb(ord.back()); else vect[0].pb(ord.back()); ord.pop_back(); } while ((max(vect[0].size(), vect[1].size())<3||min(vect[0].size(), vect[1].size())<2)&&max(vect[0].size(), vect[1].size())<X){ int a=ord.back(), b=ord[ord.size()-2], id=0; if (vect[1].size()>vect[0].size())id=1; ord.pop_back(), ord.pop_back(); int res=use_machine({vect[id][0], a, vect[id][1], b}); if (res&1)vect[!id].pb(b); else vect[id].pb(b); if (res&2)vect[!id].pb(a); else vect[id].pb(a); } while (max(vect[0].size(), vect[1].size())<X){ if (use_machine({0, ord.back()}))vect[1].pb(ord.back()); else vect[0].pb(ord.back()); ord.pop_back(); } int ans=vect[0].size(); while (ord.size()){ int id=0; if (vect[0].size()<vect[1].size())id=1; vector<int> temp; for (int i=0; i<vect[id].size()&&ord.size(); ++i)temp.pb(vect[id][i]), temp.pb(ord.back()), ord.pop_back(); int res=use_machine(temp); if (id)ans+=res/2+res%2; else ans+=temp.size()/2-(res/2+res%2); if (res%2)vect[!id].pb(temp.back()); else vect[id].pb(temp.back()); } return ans; }