| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1206135 | tkm_algorithms | Counting Mushrooms (IOI20_mushrooms) | C++20 | 0 ms | 0 KiB |
/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
//#include "mushrooms.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long
const char nl = '\n';
int count_mushrooms(int n) {
int k = 25*(sqrt(n*8)-1)/100;
vector<int> a(1), b;
int res = 1, start = 0;
for (int i = 1; i <= min(n-1, 2*k-1); ++i) {
vector<int> x = {0, i};
int cnt = use_machine(x);
if (cnt == 0){a.push_back(i); res += 1;}
else b.push_back(i);
if (sz(a) == k || sz(b) == k) {
start = i+1;
break;
}
}
if (sz(a) < k && sz(b) < k)return res;
bool ok = false;
if (sz(b) == k)swap(a, b), ok = true;
while (start < n) {
int mn = min(n-start, k);
vector<int> x;
for (int i = 0; i < mn; ++i) {
x.push_back(i+start);
x.push_back(a[i]);
}
int cnt = use_machine(x);
cnt = (cnt+1)/2;
if (ok)cnt = mn-cnt;
res += cnt;
start += k;
}
return res;
}
//int main() {
//}