Submission #1052229

#TimeUsernameProblemLanguageResultExecution timeMemory
1052229MercubytheFirst버섯 세기 (IOI20_mushrooms)C++17
56.93 / 100
6 ms600 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; using ll = long long; template <typename T> ostream& operator<<(ostream& os, const vector<T>& VEC) { os << "["; for(const auto& X : VEC) { os << X << " "; } os << "]"; return os; } constexpr int block = 100; int count_mushrooms(int n) { vector<vector<int> > g(2); g[0].push_back(0); int cur = 1; while(max(g[0].size(), g[1].size()) < block and cur < n) { g[use_machine({0, cur})].push_back(cur); cur++; } const int b = (g[0].size() >= g[1].size() ? 0 : 1); // cout << "chose : " << b << endl; assert(g[b].size() == block or cur >= n); int ans = g[0].size(); while(cur < n) { vector<int> query; for(int i = 0; i < block and cur < n; ++i) { query.push_back(g[b][i]); query.push_back(cur); cur += 1; } int x = use_machine(query); // cout << x << " : " << query << endl; if(b == 0) { ans += (query.size() / 2u) - x/2 - x%2; } else { ans += x/2 + x%2; } } return ans; } /* 8 0 1 2 3 4 5 6 7 8 9 A B B A B A A A 0 1 1 0 1 0 0 0 0 1 1 0 1 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...