# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1037099 | Raimond | Counting Mushrooms (IOI20_mushrooms) | C++17 | 7 ms | 600 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define N '\n';
#define VI <vector <int>>
#define VVI <vector <vector <int>>>
int count_mushrooms(int n){
int cnt = 1;
if(n <= 226){
for(int i = 1; i < n; i++){
cnt += 1 - use_machine({0, i});
}
return cnt;
}
vector <int> As = {0};
vector <int> Bs;
int mn = 10000, ans;
for(int i = 1; i < 500; i++){
if(2*i + ((n - (2*i)) / i) < mn){
mn = 2*i + ((n - (2*i)) / i);
ans = i;
}
}
int unt = ans*2;
// 188 - 1 = 187
for(int i = 1; i < unt; i++){
bool q = use_machine({0,i});
if(q)
Bs.push_back(i);
else
As.push_back(i);
}
cnt += As.size()-1;
int i = unt;
// n - 188 / 94
for(; i < n;){
if(As.size() >= Bs.size()){
vector<int> search;
vector <int> Is;
int j = 0;
for(; j < As.size() && i < n; j++ ){
search.push_back(i);
Is.push_back(i);
search.push_back(As[j]);
i++;
}
int q = use_machine(search);
cnt += (search.size()/2) - ((q/2) +(q % 2));
if(q/2 + q % 2 == 0){
for(int ii = 0; ii < Is.size(); ii++){
As.push_back(Is[ii]);
}
}
if(q % 2 != 0){
Bs.push_back(Is[0]);
}
}
else{
vector<int> search;
vector <int> Is;
for(int j = 0; j < Bs.size() && i < n; j++){
search.push_back(i);
Is.push_back(i);
search.push_back(Bs[j]);
i++;
}
int q = use_machine(search);
cnt += q/2 + q % 2;
if(q/2 + q % 2 == 0 ){
for(int ii = 0; ii < Is.size(); ii++){
Bs.push_back(Is[ii]);
}
}
if(q % 2 != 0){
As.push_back(Is[0]);
}
}
}
// B A B A B A
// B A A A B A B A
return cnt;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |