Submission #824023

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
824023	2023-08-13T11:32:00 Z	drdilyor	Counting Mushrooms (IOI20_mushrooms)	C++17	80.1418 / 100	8 ms	416 KB

mushrooms

#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;

int count_mushrooms(int n) {

    const int B = 281; // sqrt(4n)

    vector<int> t(n);
    t[1] = use_machine({0, 1});
    if (n == 2) return 2 - t[1] - t[0];
    t[2] = use_machine({0, 2});
    bool inv = false;
    int cmp1, cmp2;
    if (t[1] && t[2]) {
        cmp1 = 1;
        cmp2 = 2;
        inv = true;
        t[0] ^= 1;
        t[1] ^= 1;
        t[2] ^= 1;
    } else {
        cmp1 = 0;
        if (!t[1]) cmp2 = 1;
        else cmp2 = 2;
    }


    for (int i = 3; i < n-1 && i < B; i += 2) {
        int res = use_machine({cmp1, i, cmp2, i+1});
        t[i] = res / 2;
        t[i+1] = res % 2;
    }

    if (inv)
        for (int& i : t)
            i ^= 1;

    if (n < B && n % 2 == 0)
        t[n-1] = use_machine({0, n-1});

    int ans = 0;
    for (int i = 0; i < n && i < B; i++)
        if (t[i] == 0) ans++;
    if (n <= B) return ans;

    vector<int> As, Bs;
    for (int i = 0; i < B; i++) {
        if (t[i] == 0) As.push_back(i);
        else Bs.push_back(i);
    }
    vector<int> grp = As.size() > Bs.size() ? As : Bs;
    for (int j = B; j < n; j += B / 2) {
        vector<int> cur{grp.front()};
        int all_cnt = 0;
        for (int k = j; k < n && k < j + B / 2; k++) {
            cur.push_back(k);
            cur.push_back(grp[k - j + 1]);
            all_cnt++;
        }
        int cnt = use_machine(cur);
        assert(cnt % 2 == 0);
        cnt /= 2;
        if (grp == Bs) {
            ans += cnt;
        } else {
            ans += all_cnt - cnt;
        }
    }

    return ans;
}

Subtask #1

80.1418 / 100.0

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