Submission #1032369

#TimeUsernameProblemLanguageResultExecution timeMemory
1032369hotboy2703Counting Mushrooms (IOI20_mushrooms)C++17
100 / 100
6 ms600 KiB
#include "mushrooms.h" #include<bits/stdc++.h> using namespace std; using ll = int; #define pll pair <ll,ll> #define fi first #define se second #define MP make_pair #define sz(a) (ll((a).size())) #define BIT(mask,i) (((mask) >> (i))&1) #define MASK(i) (1LL<<(i)) ll use(vector <ll> tmp){ // for (auto x:tmp)cout<<x<<' '; // cout<<endl; return use_machine(tmp); } int count_mushrooms(int n) { if (n<=5){ ll res = 1; for (ll i = 1;i < n;i ++)if (use({0,i})==0)res++; return res; } vector <ll> c[2]; c[0].push_back(0); c[use({0,1})].push_back(1); c[use({0,2})].push_back(2); { ll id = 0; if (sz(c[1]) > sz(c[0]))id = 1; ll tmp = use({3,c[id][0],4,c[id][1]}); c[id ^ (tmp%2)].push_back(3); c[id ^ (tmp/2)].push_back(4); } // for (auto x:c[0])cout<<x<<' '; // cout<<'\n'; // for (auto x:c[1])cout<<x<<' '; // cout<<'\n'; ll ptr = 5; ll res = 0; while (ptr < n){ if (max(sz(c[0]),sz(c[1])) >= 100){ ll id = 0; if (sz(c[1]) > sz(c[0]))id = 1; vector <ll> tmp; for (ll j = 0;j < sz(c[id]) && ptr < n;j ++,ptr++){ tmp.push_back(c[id][j]); tmp.push_back(ptr); } ll cur = use(tmp); if (cur%2)c[1-id].push_back(tmp.back()); else c[id].push_back(tmp.back()); if (id==1)res += cur/2; else res += sz(tmp)/2 - (cur/2+1); } else{ ll id = 0; if (sz(c[1]) > sz(c[0]))id = 1; if (ptr + 4 < n){ ll tmp = use({ptr,c[id][0],ptr+1,c[id][1],ptr+2,c[id][2]}); c[id^BIT(tmp,0)].push_back(ptr); tmp-=tmp%2; // cout<<tmp<<endl; if (tmp==2){ if (sz(c[1-id]) < 2){ tmp = use({ptr+1,c[id][0],ptr+2,c[id][1]}); c[id ^ BIT(tmp,0)].push_back(ptr+1); c[id ^ BIT(tmp,1)].push_back(ptr+2); ptr+=3; } else{ tmp = use({c[!id][0],ptr+1,c[!id][1],c[id][0],ptr+2,c[id][1],ptr+3,c[id][2],ptr+4}); tmp--; // cout<<ptr<<' '<<tmp<<' '<<id<<endl; c[id^BIT(tmp,0)].push_back(ptr+4); c[id^BIT(tmp,1)].push_back(ptr+3); c[id^BIT(tmp,2)].push_back(ptr+2); c[1^id^BIT(tmp,2)].push_back(ptr+1); ptr+=5; } } else{ c[id^(tmp>0)].push_back(ptr+1); c[id^(tmp>0)].push_back(ptr+2); ptr+=3; } } else if (ptr + 1 < n){ ll tmp = use({ptr,c[id][0],ptr+1,c[id][1]}); c[id ^ BIT(tmp,0)].push_back(ptr); c[id ^ BIT(tmp,1)].push_back(ptr+1); ptr+=2; } else{ c[use({0,ptr})].push_back(ptr); ptr++; } } } // for (auto x:c[0])cout<<x<<' '; // cout<<'\n'; // for (auto x:c[1])cout<<x<<' '; // cout<<'\n'; res += sz(c[0]); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...