Submission #410938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410938	2021-05-23T22:44:58 Z	534351	Counting Mushrooms (IOI20_mushrooms)	C++17	89.3281 / 100	10 ms	356 KB

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 = 85;
    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

89.3281 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	3 ms	300 KB	Output is correct
6	Correct	2 ms	200 KB	Output is correct
7	Correct	6 ms	352 KB	Output is correct
8	Correct	10 ms	328 KB	Output is correct
9	Correct	8 ms	352 KB	Output is correct
10	Correct	8 ms	328 KB	Output is correct
11	Partially correct	8 ms	344 KB	Output is partially correct
12	Correct	7 ms	328 KB	Output is correct
13	Correct	9 ms	336 KB	Output is correct
14	Correct	5 ms	324 KB	Output is correct
15	Partially correct	8 ms	328 KB	Output is partially correct
16	Partially correct	8 ms	328 KB	Output is partially correct
17	Correct	5 ms	328 KB	Output is correct
18	Correct	7 ms	328 KB	Output is correct
19	Partially correct	6 ms	352 KB	Output is partially correct
20	Correct	8 ms	328 KB	Output is correct
21	Correct	6 ms	356 KB	Output is correct
22	Partially correct	8 ms	328 KB	Output is partially correct
23	Correct	7 ms	328 KB	Output is correct
24	Correct	5 ms	336 KB	Output is correct
25	Partially correct	8 ms	332 KB	Output is partially correct
26	Partially correct	9 ms	328 KB	Output is partially correct
27	Partially correct	7 ms	328 KB	Output is partially correct
28	Partially correct	9 ms	332 KB	Output is partially correct
29	Partially correct	7 ms	340 KB	Output is partially correct
30	Partially correct	8 ms	348 KB	Output is partially correct
31	Partially correct	9 ms	352 KB	Output is partially correct
32	Partially correct	8 ms	328 KB	Output is partially correct
33	Partially correct	8 ms	308 KB	Output is partially correct
34	Partially correct	8 ms	328 KB	Output is partially correct
35	Partially correct	8 ms	344 KB	Output is partially correct
36	Partially correct	7 ms	328 KB	Output is partially correct
37	Partially correct	9 ms	304 KB	Output is partially correct
38	Partially correct	8 ms	328 KB	Output is partially correct
39	Partially correct	6 ms	352 KB	Output is partially correct
40	Partially correct	8 ms	340 KB	Output is partially correct
41	Partially correct	8 ms	328 KB	Output is partially correct
42	Partially correct	7 ms	328 KB	Output is partially correct
43	Partially correct	6 ms	356 KB	Output is partially correct
44	Partially correct	8 ms	332 KB	Output is partially correct
45	Partially correct	7 ms	336 KB	Output is partially correct
46	Partially correct	9 ms	328 KB	Output is partially correct
47	Partially correct	8 ms	328 KB	Output is partially correct
48	Partially correct	8 ms	356 KB	Output is partially correct
49	Partially correct	7 ms	328 KB	Output is partially correct
50	Partially correct	8 ms	328 KB	Output is partially correct
51	Partially correct	8 ms	332 KB	Output is partially correct
52	Partially correct	9 ms	328 KB	Output is partially correct
53	Partially correct	8 ms	316 KB	Output is partially correct
54	Partially correct	7 ms	332 KB	Output is partially correct
55	Partially correct	10 ms	328 KB	Output is partially correct
56	Partially correct	9 ms	328 KB	Output is partially correct
57	Partially correct	8 ms	328 KB	Output is partially correct
58	Partially correct	8 ms	344 KB	Output is partially correct
59	Partially correct	9 ms	328 KB	Output is partially correct
60	Partially correct	9 ms	352 KB	Output is partially correct
61	Partially correct	8 ms	328 KB	Output is partially correct
62	Correct	1 ms	200 KB	Output is correct
63	Correct	1 ms	200 KB	Output is correct
64	Correct	1 ms	200 KB	Output is correct
65	Correct	1 ms	200 KB	Output is correct
66	Correct	1 ms	200 KB	Output is correct
67	Correct	1 ms	200 KB	Output is correct
68	Correct	1 ms	200 KB	Output is correct
69	Correct	1 ms	200 KB	Output is correct
70	Correct	1 ms	200 KB	Output is correct
71	Correct	1 ms	200 KB	Output is correct
72	Correct	1 ms	200 KB	Output is correct
73	Correct	1 ms	200 KB	Output is correct
74	Correct	1 ms	324 KB	Output is correct
75	Correct	1 ms	200 KB	Output is correct
76	Correct	1 ms	200 KB	Output is correct
77	Correct	1 ms	200 KB	Output is correct
78	Correct	1 ms	200 KB	Output is correct
79	Correct	1 ms	200 KB	Output is correct
80	Correct	1 ms	200 KB	Output is correct
81	Correct	1 ms	200 KB	Output is correct
82	Correct	1 ms	200 KB	Output is correct
83	Correct	1 ms	200 KB	Output is correct
84	Correct	1 ms	200 KB	Output is correct
85	Correct	1 ms	200 KB	Output is correct
86	Correct	1 ms	200 KB	Output is correct
87	Correct	1 ms	200 KB	Output is correct
88	Correct	1 ms	200 KB	Output is correct
89	Correct	1 ms	200 KB	Output is correct
90	Correct	1 ms	200 KB	Output is correct
91	Correct	1 ms	200 KB	Output is correct