Submission #410939

#	Time	Username	Problem	Language	Result	Execution time	Memory
410939		534351	Counting Mushrooms (IOI20_mushrooms)	C++17	88.63 / 100	11 ms	456 KiB

mushrooms

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int ask(vi v)
{
    if (SZ(v) <= 1) return 0;
    return use_machine(v);
}

int N, ans;
vi as, bs;

int count_mushrooms(int n)
{
    N = n;
    vi v(2);
    v[0] = 0;
    if (N < 10)
    {
        ans = 1;
        FOR(i, 1, N)
        {
            v[1] = i;
            int q = ask(v);
            if (q != 1) ans++;
        }
        return ans;
    }
    as.PB(0);
    FOR(i, 1, 4)
    {
        v[1] = i;
        int q = ask(v);
        if (q == 1)
        {
            bs.PB(i);
        }
        else
        {
            as.PB(i);
        }
    }
    int MAGIC = 4, LIMIT = 88;
    v.clear();
    while(MAGIC + 1 < N && SZ(as) < LIMIT && SZ(bs) < LIMIT)
    {
        if (SZ(bs) >= 2)
        {
            v = {MAGIC, bs[0], MAGIC + 1, bs[1]};
            int c = ask(v);
            if (c == 0)
            {
                bs.PB(MAGIC);
                bs.PB(MAGIC + 1);
            }
            if (c == 1)
            {
                as.PB(MAGIC);
                bs.PB(MAGIC + 1);
            }
            if (c == 2)
            {
                bs.PB(MAGIC);
                as.PB(MAGIC + 1);
            }
            if (c == 3)
            {
                as.PB(MAGIC);
                as.PB(MAGIC + 1);
            }
        }
        else
        {
            v = {MAGIC, as[0], MAGIC + 1, as[1]};
            int c = ask(v);
            if (c == 0)
            {
                as.PB(MAGIC);
                as.PB(MAGIC + 1);
            }
            if (c == 1)
            {
                bs.PB(MAGIC);
                as.PB(MAGIC + 1);
            }
            if (c == 2)
            {
                as.PB(MAGIC);
                bs.PB(MAGIC + 1);
            }
            if (c == 3)
            {
                bs.PB(MAGIC);
                bs.PB(MAGIC + 1);
            }
        }
        MAGIC += 2;
    }
    ans = SZ(as);
    if (SZ(bs) > SZ(as))
    {
        //we'll be counting how many bs there are in here.
        while(MAGIC < N)
        {
            vi tmp = bs;
            v.clear();
            int lol = MAGIC;
            v.PB(MAGIC);
            v.PB(tmp.back());
            tmp.pop_back();
            MAGIC++;
            while(MAGIC < N && !tmp.empty())
            {
                v.PB(MAGIC);
                v.PB(tmp.back());
                tmp.pop_back();
                MAGIC++;
            }
            int c = ask(v);
            ans += (c / 2) + (c % 2);
            if (c % 2)
            {
                as.PB(lol);
            }
            else
            {
                bs.PB(lol);
            }
        }
    }
    else
    {
        while(MAGIC < N)
        {
            vi tmp = as;
            v.clear();
            v.PB(MAGIC);
            int lol = MAGIC;
            v.PB(tmp.back());
            tmp.pop_back();
            MAGIC++;
            ans++;
            while(MAGIC < N && !tmp.empty())
            {
                v.PB(MAGIC);
                v.PB(tmp.back());
                tmp.pop_back();
                MAGIC++;
                ans++;
            }
            int c = ask(v);
            ans -= ((c / 2) + (c % 2));
            if (c % 2)
            {
                bs.PB(lol);
            }
            else
            {
                as.PB(lol);
            }
        }
    }
    return ans;
    // std::vector<int> m;
    // for (int i = 0; i < n; i++)
    // 	m.push_back(i);
    // int c1 = use_machine(m);
    // m = {0, 1};
    // int c2 = use_machine(m);
    // return c1+c2;
}

• Subtask 1: 88.6275 / 100