| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 312981 | kobus | Counting Mushrooms (IOI20_mushrooms) | C++17 | 0 ms | 0 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<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define MAXN 1123
#define INF (int)1.5e12
#define INFF LLONG_MAX/2
#define eps 1e-4
#include "mushrooms.h"
int count_mushrooms(int n){
vector<int> s[2]={{0},{}};
int nn[2]={0,0};
vector<int> ns;
for(int i=1;i<n;i++)ns.pb(i);
int k=85;
while(ns.size()>0){
if(k>0 && ns.size()>1 && max(s[0].size(),s[1].size())>1){
k--;
int a=ns[ns.size()-1];
int b=ns[ns.size()-2];
ns.pop_back();
ns.pop_back();
bool si=1;
if(s[0].size()>s[1].size())si=0;
int v[4]={s[si][0],a,s[si][1],b};
int x=use_machine(v);
if(x%2)s[!si].pb(b);
else s[si].pb(b);
x=x/2;
if(x%2)s[!si].pb(a);
else s[si].pb(a);
}
else{
bool si=1;
if(s[0].size()>s[1].size())si=0;
int tam=min(s[si].size(),ns.size());
int v[2*tam];
for(int i=0;i<tam;i++){
v[2*i]=s[si][i];
}
for(int i=0;i<tam;i++){
v[2*i+1]=ns[ns.size()-i-1];
}
for(int i=0;i<tam;i++)ns.pop_back();
int x=use_machine(v);
if(x%2)s[!si].pb(v[2*tam-1]);
else s[si].pb(v[2*tam-1]);
x=x/2;
nn[!si]+=x;
nn[si]+=tam-1-x;
}
}
return s[0].size()+nn[0];
}