제출 #830768

#제출 시각아이디문제언어결과실행 시간메모리
830768amunduzbaev버섯 세기 (IOI20_mushrooms)C++17
53.68 / 100
10 ms364 KiB
#include "mushrooms.h" #include "bits/stdc++.h" using namespace std; #define ar array typedef long long ll; //~ #define int ll const int N = 20'000; int count_mushrooms(int n){ int B = 142; //~ for(int i=1;i<=N;i++){ //~ if(2 * i + (N + i - 1) / i < 2 * B + (N + B - 1) / B){ //~ B = i; //~ } //~ } vector<int> p[2]; p[0].push_back(0); int last = 1; for(int i=1;i<n && max((int)p[0].size(), (int)p[1].size()) < B;i++){ last++; if(i + 1 < n){ last++; int c = use_machine({i, 0, i + 1}); if(c == 0) p[0].push_back(i), p[0].push_back(i + 1); if(c == 2) p[1].push_back(i), p[1].push_back(i + 1); if(c == 1){ if(use_machine({0, i})) p[1].push_back(i), p[0].push_back(i + 1); else p[0].push_back(i), p[1].push_back(i + 1); } i++; continue; } if(use_machine({0, i})) p[1].push_back(i); else p[0].push_back(i); } ar<int, 2> cc {}; cc[0] = p[0].size(), cc[1] = p[1].size(); bool is = 1; if(p[0].size() < p[1].size()) is = 0; for(int i=last;i<n;){ int j = min(i + B - 1, n); vector<int> qq; for(int k=i;k<j;k++){ qq.push_back(p[is ^ 1][k - i]); qq.push_back(k); } qq.push_back(p[is ^ 1].back()); int c = use_machine(qq) / 2; cc[is] += c, cc[is ^ 1] += (j - i - c); i = j; } return cc[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...