Submission #1018988

#TimeUsernameProblemLanguageResultExecution timeMemory
1018988j_vdd16Counting Mushrooms (IOI20_mushrooms)C++17
25 / 100
87 ms600 KiB
#include "mushrooms.h" #include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; //int use_machine(vi x); int count_mushrooms(int n) { vi a = { 0 }; vi b; int i = 1; /*for (; i < n; i++) { int res = use_machine({ 0, i }); if (res == 0) a.push_back(i); else b.push_back(i); if (a.size() >= 2 && 2 * a.size() * a.size() >= n) break; if (b.size() >= 2 && 2 * b.size() * b.size() >= n) break; } i++;*/ int result = a.size(); while (i < n) { if (a.size() > b.size()) { int sq = a.size(); vi ask; int asked = min(sq, n - i); loop(j, asked) { ask.push_back(a[j]); ask.push_back(i++); } int res = use_machine(ask); result += asked - res / 2 - res % 2; if (res % 2) b.push_back(i - 1); } else { int sq = b.size(); vi ask; loop(j, min(sq, n - i)) { ask.push_back(b[j]); ask.push_back(i++); } int res = use_machine(ask); result += res / 2 + res % 2; if (res % 2) a.push_back(i - 1); } } //226 ~ log_2(20000)^2 //226 / Q * 100 = 52,68 //226 * 100 / 52,68 = 429 //S = 2 * sqrt(n); //S + (n - S) / sqrt(n) //2sqrt(n) + sqrt(n) - 2 //3sqrt(n) //min: 2 * n^x + (n - 2 * n^x) / n^x //min: 2 * n^x + n^(1 - x) >= 2 * sqrt(2 * n) return result; }
#Verdict Execution timeMemoryGrader output
Fetching results...