Submission #772718

#TimeUsernameProblemLanguageResultExecution timeMemory
772718cadmiumskyCounting Mushrooms (IOI20_mushrooms)C++17
80.71 / 100
7 ms432 KiB
#include <bits/stdc++.h> #include "mushrooms.h" #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; int f(int x) { return (x + 1) / 2; } int count_mushrooms(int n) { srand(time(0)); int cnt[2] = {1, 0}; vector<int> known[2]; known[0].emplace_back(0); for(int i = 1; i < n;) { int T = (sz(known[0]) > sz(known[1])? 0 : 1); vector<int> cquery; int j; for(j = i; j < n && j - i < sz(known[T]); j++) cquery.emplace_back(known[T][j - i]), cquery.emplace_back(j); bool bulaneala = 0; if(known[T ^ 1].size()) { if(rand() % 2) { bulaneala = 1; cquery.back() = known[T ^ 1][rand() % sz(known[T ^ 1])]; cquery.emplace_back(j - 1); } } i = i + sz(known[T]); //cerr << i << ":\n"; //for(auto x : cquery) cerr << x << ' '; int A = use_machine(cquery) - bulaneala; if(bulaneala) A ^= 1; //cerr << "\n" << A << "\n--\n"; cnt[T ^ 1] += f(A); cnt[T] += sz(cquery) / 2 - f(A); known[T ^ (A % 2)].emplace_back(cquery.back()); } return cnt[0]; } /** Anul asta se da centroid. -- Surse oficiale */
#Verdict Execution timeMemoryGrader output
Fetching results...