#include "mushrooms.h" #include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) #define BLOCK 150 int count_mushrooms(int n) { int ans=1; vi a; vi b; a.push_back(0); int last=0; FORi(i,1,n){ if(a.size()>=BLOCK || b.size()>=BLOCK) break; if((a.size()<2 && b.size()<2) || i+1>=n){ int x = use_machine({0,i}); if(x) b.push_back(i); else a.push_back(i), ans++; } else{ vi c; if(a.size()>=2) c = a; else c = b; int x = use_machine({c[0], i, c[1], i+1}); if(a.size()>=2) ans+=max(2-x, 0); else ans+=max(x-1, 0), x = 3-x; if(x==0) a.push_back(i), a.push_back(i+1); else if(x==1) a.push_back(i), b.push_back(i+1); else if(x==2) b.push_back(i), a.push_back(i+1); else if(x==3) b.push_back(i), b.push_back(i+1); i++; } last = i; } vi c; if(a.size()==BLOCK) c = a; else c = b; FORi(i,last+1,n){ if(i+BLOCK-1<n){ vi m; FOR(j,BLOCK) m.push_back(c[j]), m.push_back(i+j); int x = use_machine(m); int cur = 0; cur+= BLOCK - (x+1)/2; if(a.size()==BLOCK) ans+=cur; else ans+=BLOCK-cur; i+=BLOCK-1; } else{ ans += 1 - use_machine({0,i}); } } return ans; }