Submission #1127353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127353		jerzyk	Counting Mushrooms (IOI20_mushrooms)	C++20	97 / 100	4 ms	460 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;
int l = 0;

void Opt0()
{
    //cerr << ans << " " << " Opt0 \n";
    int a = cur, b = cur + 1, c = cur + 2;
    cur += 3;
    vector<int>q{pos0[0], a, pos0[1], b, pos0[2], c};
    int x = use_machine(q);
    //cerr << a << " " << b << " " << c << " " << x << "\n"; 
     if(x % 2 == 1)
    {
        pos1.pb(c);
        x -= 1;
    }else
    {
        pos0.pb(c); ++ans;
    }
    if(x == 0)
    {
        pos0.pb(a); pos0.pb(b);
        ans += 2;
        return;
    }
    if(x == 4)
    {
        pos1.pb(a); pos1.pb(b);
        return;
    }
    ++l;
    c = cur; int d = cur + 1;
    cur += 2;
    q = {pos0[0], d, pos0[1], a, pos0[2], pos1[0], b, pos1[1], c};
    x = use_machine(q);
    //cerr << "Q2: " << x << "\n";
    //cerr << pos0[1] << " " << pos0[2] << "\n";
    //cerr << a << " " << b << " " << d << " " << c << "\n";
    if(x % 2 == 1)
    {
        pos1.pb(c);
    }else
    {
        x -= 1;
        pos0.pb(c); ++ans;
    }
    --x;
    if(x % 4 == 0)
    {
        ++ans;
        pos0.pb(d);
    }else
    {
        x -= 2;
        pos1.pb(d);
    }
    ++ans;
    if(x == 4)
    {
        pos1.pb(a);
        pos0.pb(b);
    }else
    {
        pos1.pb(b);
        pos0.pb(a);
    }
}

void Opt1()
{
    //cerr << "Opt1\n";
    //cerr << cur << "\n";
    int a = cur, b = cur + 1, c = cur + 2;
    cur += 3;
    vector<int>q{pos1[0], a, pos1[1], b, pos1[2], c};
    int x = use_machine(q);
    if(x % 2 == 1)
    {
        pos0.pb(c); ++ans;
        x -= 1;
    }else
    {
        pos1.pb(c);
    }
    if(x == 0)
    {
        pos1.pb(a); pos1.pb(b);
        return;
    }
    if(x == 4)
    {
        pos0.pb(a); pos0.pb(b);
        ans += 2;
        return;
    }
    ++l;
    c = cur; int d = cur + 1;
    cur += 2;
    q = {pos1[0], d, pos1[1], a, pos1[2], pos0[0], b, pos0[1], c};
    x = use_machine(q);
    if(x % 2 == 1)
    {
        pos0.pb(c);
        ++ans;
    }else
    {
        x -= 1;
        pos1.pb(c);
    }
    --x;
    if(x % 4 == 0)
    {
        pos1.pb(d);
    }else
    {
        x -= 2;
        ++ans;
        pos0.pb(d);
    }
    ++ans;
    if(x == 4)
    {
        pos0.pb(a);
        pos1.pb(b);
    }else
    {
        pos0.pb(b);
        pos1.pb(a);
    }
}

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);

    //cerr << "XD\n";
    if((int)pos0.size() < 2 && cur <= n)
        Ask0();
    for(int i = 0; i < 2 && cur <= n - 1; ++i)
        if((int)pos0.size() >= 2)
            Q20();
        else
            Q21();
    while((((int)pos0.size() < 2 || (int)pos1.size() < 2) || ((int)pos0.size() < 3 && (int)pos1.size() < 3)) && cur <= n)
        if((int)pos0.size() > (int)pos1.size())
            Ask0();
        else
            Ask1();
    //cerr << pos0.size() << " " << pos1.size() << " xd\n";
    for(int l = 1; l <= 60 && cur <= n - 4; ++l)
    {
        if((int)pos0.size() >= 3)
            Opt0();
        else 
            Opt1();
    }
    while(cur <= n)
    {
        if((int)pos0.size() >= (int)pos1.size())
            Ask0();
        else
            Ask1();
    }
    return ans;
}

• Subtask 1: 96.9957 / 100