Submission #1125504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125504		jerzyk	Counting Mushrooms (IOI20_mushrooms)	C++20	91.87 / 100	4 ms	444 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
vector<int> pos0, pos1;
int cur = 2, n, ans = 1;

void Q20()
{
    vector<int> q;
    q.pb(pos0[0]);
    q.pb(cur); ++cur;
    q.pb(pos0[1]);
    q.pb(cur); ++cur;
    int x = use_machine(q);
    if(x % 2 == 0)
    {
        ++ans; pos0.pb(q.back());
    }else
    {
        pos1.pb(q.back());
        --x;
    }
    if(x == 0)
    {
        ++ans; pos0.pb(q[1]);
    }else
    {
        pos1.pb(q[1]);
    }
}

void Q21()
{
    vector<int> q;
    q.pb(pos1[0]);
    q.pb(cur); ++cur;
    q.pb(pos1[1]);
    q.pb(cur); ++cur;
    int x = use_machine(q);
    if(x % 2 == 0)
    {
        pos1.pb(q.back());
    }else
    {
        pos0.pb(q.back());
        ++ans;
        --x;
    }
    if(x == 0)
    {
        pos1.pb(q[1]);
    }else
    {
        pos0.pb(q[1]);
        ++ans;
    }
}

void Ask0()
{
    vector<int> q;
    for(int l = 0; l < (int)pos0.size() && cur <= n; ++l)
    {
        q.pb(pos0[l]);
        q.pb(cur);
        ++cur;
    }
    int x = use_machine(q);
    if(x % 2 == 0)
    {
        pos0.pb(q.back());
    }else
    {
        ++x;
        pos1.pb(q.back());
    }
    ans += ((int)q.size() - x) / 2;
}

void Ask1()
{
    vector<int> q;
    for(int l = 0; l < (int)pos1.size() && cur <= n; ++l)
    {
        q.pb(pos1[l]);
        q.pb(cur);
        ++cur;
    }
    int x = use_machine(q);
    if(x % 2 == 1)
    {
        ++x;
        pos0.pb(q.back());
    }else
    {
        pos1.pb(q.back());
    }
    ans += x / 2;
}

int count_mushrooms(int _n)
{
    n = _n - 1;
    int x = use_machine({0, 1});
    pos0.pb(0);
    if(x % 2 == 0)
    {
        ++ans;
        pos0.pb(1);
    }
    else
        pos1.pb(1);
    if((int)pos0.size() == 1 && cur <= n)
        Ask0();
    for(int l = 1; l <= 100 && cur <= n - 1; ++l)
    {
        if((int)pos0.size() >= 2)
            Q20();
        else 
            Q21();
    }
    while(cur <= n)
    {
        if((int)pos0.size() >= (int)pos1.size())
            Ask0();
        else
            Ask1();
    }
    return ans;
}

• Subtask 1: 91.8699 / 100