Submission #306892

#TimeUsernameProblemLanguageResultExecution timeMemory
306892ivan24Counting Mushrooms (IOI20_mushrooms)C++14
25 / 100
107 ms744 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; using ll = int; typedef vector<ll> vi; typedef vector<vi> vvi; typedef pair<ll,ll> ii; typedef vector<ii> vii; typedef vector<vii> vvii; #define F first #define S second class Solver{ private: ll n; vi type, ctr; vvi byType; void add_type(ll x, bool t){ if (n <= x || type[x] != -1) return; type[x] = t; byType[t].push_back(x); ctr[t]++; } void addOne(ll x){ ll res = use_machine(vi{0,x}); add_type(x,res); } void addTwo(ll x, ll y){ //cout << x << " " << y << endl; bool t = 0; if (byType[0].size() < 2){ t = 1; } //cout << t << " " << byType[t].size() << endl; ll res = use_machine(vi{x,byType[t][0],y,byType[t][1]}); add_type(x,(res&1) ? !t : t); add_type(y,(res&2) ? !t : t); } public: Solver(ll n): n(n), type(n,-1), ctr(2,0), byType(2){ type[0] = 0; ctr[0]++; byType[0].push_back(0); } int solve(){ //cout << "hello\n"; addOne(1); if (n > 2){ addOne(2); for (ll i = 2; n > 2*i; i++){ addTwo(2*i-1,2*i); } //cout << "hello\n"; if (type[n-1] == -1){ addOne(n-1); } } return ctr[0]; } }; int count_mushrooms(int n) { Solver mySolver(n); return mySolver.solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...