Submission #1125496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125496		jerzyk	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	4 ms	464 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 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);
    while(cur <= n)
    {
        if((int)pos0.size() >= (int)pos1.size())
            Ask0();
        else
            Ask1();
    }
    return ans;
}

• Subtask 1: 80.7143 / 100