Submission #306919

#TimeUsernameProblemLanguageResultExecution timeMemory
306919ivan24Counting Mushrooms (IOI20_mushrooms)C++14
0 / 100
3 ms512 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); } bool big_query (){ bool t = ((byType[0].size() > byType[1].size()) ? 0 : 1); ll min_idx = ctr[0]+ctr[1]; ll max_idx = min_idx + byType[t].size()-1; if (min_idx == n) return false; vi v; for (ll i = min_idx; max_idx >= i && n > i; i++){ v.push_back(i); v.push_back(byType[t][i-min_idx]); } ll res = use_machine(v); if (res%2 == 1){ res--; add_type(min_idx,!t); }else add_type(min_idx,t); ctr[!t] += res/2; ctr[t] += byType[t].size()-res/2; } 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 = 0; 140 > 2*i+4 && n > 2*i+4; i++){ addTwo(2*i+3,2*i+4); } //cout << "hello\n"; if (type[n-1] == -1){ addOne(n-1); } while(big_query()){} } return ctr[0]; } }; int count_mushrooms(int n) { Solver mySolver(n); return mySolver.solve(); }

Compilation message (stderr)

mushrooms.cpp: In member function 'bool Solver::big_query()':
mushrooms.cpp:49:12: warning: control reaches end of non-void function [-Wreturn-type]
   49 |         vi v;
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...