# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
824755 | fatemetmhr | Counting Mushrooms (IOI20_mushrooms) | C++17 | 7 ms | 312 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.
// Be name khoda //
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "(" << #x << "):" << x << endl;
#define all(x) x.begin(), x.end();
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int ssq = 141;
const int maxn5 = 1e5 + 10;
vector <int> av, av2;
int cnt[2], ty[maxn5];
int count_mushrooms(int n){
av = {0, 1};
int a = use_machine(av);
ty[0] = 0;
ty[1] = a;
if(n == 2){
if(a)
return 1;
return 2;
}
av = {0, 2};
int b = use_machine(av);
ty[2] = b;
int x1, x2;
if(a == 0){
x1 = 0;
x2 = 1;
}
else if(b == 0){
x1 = 0;
x2 = 2;
}
else{
x1 = 1;
x2 = 2;
}
//cout << x1 << ' ' << x2 << endl;
cnt[0] = 1 + (1 ^ ty[2]) + (1 ^ ty[1]);
cnt[1] = ty[2] + ty[1];
int pt = 3;
while(max(cnt[0], cnt[1]) < ssq && cnt[0] + cnt[1] < n){
if(pt + 1 == n){
av = {x1, pt};
int x = use_machine(av);
ty[pt] = (ty[x1] ^ x);
cnt[ty[pt]]++;
pt++;
continue;
}
av = {x1, pt, x2, pt + 1};
int x = use_machine(av);
if(x == 0){
ty[pt] = ty[pt + 1] = ty[x1];
cnt[ty[x1]] += 2;
}
if(x == 1){
ty[pt] = ty[x1];
ty[pt + 1] = ty[x1] ^ 1;
cnt[ty[x1]]++;
cnt[ty[x1] ^ 1]++;
}
if(x == 2){
ty[pt] = ty[x1] ^ 1;
ty[pt + 1] = ty[x1];
cnt[ty[x1]]++;
cnt[ty[x1] ^ 1]++;
}
if(x == 3){
ty[pt] = ty[pt + 1] = ty[x1] ^ 1;
cnt[ty[x1] ^ 1] += 2;
}
pt += 2;
}
if(cnt[0] + cnt[1] == n)
return cnt[0];
int g = 0;
if(cnt[1] > cnt[0])
g = 1;
for(int i = 0; i < pt; i++) if(ty[i] == g)
av2.pb(i);
//cout << pt << ' ' << g << ' ' << av2.size() << endl;
while(pt < n){
av.clear();
int ind = 0;
while(pt < n && ind < av2.size()){
av.pb(av2[ind++]);
av.pb(pt++);
}
int x = use_machine(av);
int num = x / 2 + x % 2;
cnt[g ^ 1] += num;
cnt[g] += int(av.size()) / 2 - num;
}
return cnt[0];
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |