Submission #1035705

#TimeUsernameProblemLanguageResultExecution timeMemory
1035705Mr_HusanboyCounting Mushrooms (IOI20_mushrooms)C++17
53.81 / 100
7 ms600 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define all(a) (a).begin(), (a).end() #define ff first #define ss second template<typename T> int len(T &a){return a.size();} mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); int count_mushrooms(int n) { if(n < 10){ int ans = 1; for(int i = 1; i < n; i ++){ ans += use_machine({0, i}) ^ 1; } return ans; } int sq = sqrt(n); int i = 1; vector<int> a = {0}, b; while(len(a) < sq && len(b) < sq){ if(use_machine({0, i})){ b.push_back(i); }else{ a.push_back(i); } i ++; } if(len(a) >= sq){ ll ans = len(a); while(i < n){ vector<int> req; for(int j = 0; j < len(a) && i < n; j ++){ req.push_back(a[j]); req.push_back(i); i ++; } // for(auto u : req) cout << u << ' '; // cout << endl; ans += len(req) / 2 - (use_machine(req) + 1) / 2; } return ans; }else{ ll ans = len(a); while(i < n){ vector<int> req; for(int j = 0; j < len(b) && i < n; j ++){ req.push_back(b[j]); req.push_back(i); i ++; } ans += (use_machine(req) + 1) / 2; } return ans; } }
#Verdict Execution timeMemoryGrader output
Fetching results...