제출 #833988

#제출 시각아이디문제언어결과실행 시간메모리
833988Johann버섯 세기 (IOI20_mushrooms)C++14
87.94 / 100
7 ms336 KiB
#include "mushrooms.h" #include "bits/stdc++.h" using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() int count_mushrooms(int n) { vi m; // 0 for a and 1 for b vvi sure(2); vi cnt(2, 0); sure[0].push_back(0); cnt[0] = 1; int idx = 1; while (idx < n && max(sz(sure[0]), sz(sure[1])) < 2) { assert(sz(sure[0]) > 0); m.clear(); m.push_back(sure[0].front()); m.push_back(idx++); int c1 = use_machine(m); ++cnt[c1], sure[c1].push_back(m.back()); } while (idx < n && max(sz(sure[0]), sz(sure[1])) < sqrt(n) - 1) { int i = (sz(sure[0]) < sz(sure[1])); m.clear(); for (int j = 0; j < 2; ++j) { m.push_back(sure[i][j]); if (idx < n) m.push_back(idx++); } int c2 = use_machine(m); ++cnt[i ^ (c2 / 2)], sure[i ^ (c2 / 2)].push_back(m[1]); if (sz(m) > 3) ++cnt[i ^ (c2 & 1)], sure[i ^ (c2 & 1)].push_back(m[3]); } while (idx < n) { int i = (sz(sure[0]) < sz(sure[1])); m.clear(); for (int j = 0; j < sz(sure[i]) && idx < n; ++j) { m.push_back(sure[i][j]); m.push_back(idx++); } int c3 = use_machine(m); int lenCnt = (sz(m) - 2) / 2; cnt[i] += lenCnt - (c3 / 2); cnt[i ^ 1] += c3 / 2; ++cnt[i ^ (c3 & 1)], sure[i ^ (c3 & 1)].push_back(m.back()); } return cnt[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...