Submission #531755

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531755	2022-03-01T11:36:28 Z	EqualTurtle	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	8 ms	328 KB

mushrooms

#include<bits/stdc++.h>
#include "mushrooms.h"
#define notw (which+1)%2
#define zero1 sure[which][0]
#define zero2 sure[which][1]
#define zero3 sure[which][2]
#define zero4 sure[which][3]
#define one1 sure[notw][0]
#define A counter
#define B counter+1
#define C counter+2
#define D counter+3
#define E counter+4
using namespace std;

constexpr int maxk = 120;
vector <int> sure[2];
int res = 0;
int which, counter;

void assign(vector <int> v, int st)
{
    for (int i = 0; i < (int)v.size(); i++)
        sure[which ^ v[i]].push_back(st + i);
}

void quick_update()
{
    which = (sure[0].size() >= sure[1].size() ? 0 : 1);
    counter = sure[0].size() + sure[1].size();
}

void debug()
{
    for (int i : sure[0])
        cout << i << " ";
    cout << "\n";
    for (int i : sure[1])
        cout << i << " ";
    cout << "\n";

    cout << "-----------------\n";
}

void first_two()
{
    vector <int> arr = {0, 1};
    int curr = use_machine(arr);
    if (!curr){
        sure[0].push_back(1);
        return;
    }
    sure[1].push_back(1);
    arr = {0, 2};
    curr = use_machine(arr);

    if (curr == 0)
        sure[0].push_back(2);
    else
        sure[1].push_back(2);
}

void phase1_1(int k)
{
    quick_update();
    while (((int)sure[which].size() < 4 || (int)sure[notw].size() == 0) && ((int)sure[which].size() <= k)) // untill i have 4 zeros and 1 one
    {
        int curr = use_machine({zero1, A, B, C, D, E});

        if (curr == 0)
            assign({0, 0, 0, 0, 0}, A);
        else if (curr == 5)
            assign({1, 0, 1, 0, 1}, A);
        else if (curr == 1)
        {
            int curr2 = use_machine({0, B});
            if (curr2 == 1){
                curr2 = use_machine({0, A});
                assign({curr2, 1, 1, 1, 1}, A);
            }
            else{
                curr2 = use_machine({0, C, B, D});
                assign({0, 0, curr2 / 2, curr2 % 2, 1}, A);
            }
        }
        else if (curr == 3)
        {
            int curr2 = use_machine({0, D, C});
            if (curr2 % 2 == 0)
            {
                int curr3 = use_machine({0, A, C, B});
                assign({curr3 / 2, curr3 % 2, 0, curr2 / 2, 1}, A);
            }
            else
            {
                int curr3 = use_machine({E, A, C, B});
                assign({(curr3 / 2) == 0, (curr3 % 2) == 0, 1, curr3 == 1, 1}, A);
            }
        }
        else // curr % 2 == 0
        {
            int curr2 = use_machine({0, A, E, B});
            int curr3 = use_machine({0, C, E, D});
            assign({curr2 / 2, curr2 % 2, curr3 / 2, curr3 % 2, 0}, A);
        }

        quick_update();
    }
}

void phase1_2(int k)
{
    quick_update();
    while ((int)sure[which].size() <= k) // untill i have k zeros or ones
    {
        int curr = use_machine({A, zero1, B, zero2, C, D, one1, E});
        if (curr == 1){
            curr = use_machine({zero1, C, zero2, D});
            assign({0, 0, curr / 2, curr % 2, 1}, A);
        }
        else if (curr == 2){
            curr = use_machine({zero1, C, zero2, D, zero3, E});
            assign({curr % 2, 0, curr >= 4, curr >= 2, curr % 2}, A);
        }
        else if (curr == 3){
            curr = use_machine({C, zero1, B, zero2, E, zero3, D});

            if (curr == 3)
                assign({0, 0, 1, 0, 1}, A);
            else
                assign({curr < 3, curr > 3, (curr % 4) == 2, (curr % 4) != 0, curr > 3}, A);
        }
        else if (curr == 4){
            curr = use_machine({C, zero1, A, zero2, D, zero3, E, zero4});
            assign({curr / 4, (curr % 4) != 1, curr % 2, (curr % 4) / 2, curr / 4}, A);
        }
        else if (curr == 5){
            curr = use_machine({A, zero1, C, zero2, D, zero3, E, zero4, B});
            assign({curr != 5, curr != 3, (curr != 2 && curr != 4), (curr == 6 || curr == 4), curr == 5}, A);
        }
        else if (curr == 6){
            curr = use_machine({zero1, A});
            assign({curr, 1, 1, 0, curr}, A);
        }
        else // curr == 7
            assign({1, 1, 1, 0, 0}, A); 

        quick_update();
    }
}

void phase2(int n)
{
    quick_update();

    while (counter < n)
    {
        int siz = min(n - counter, (int)sure[which].size());
 
        vector <int> arr;
        for (int i = 0; i < siz; i++){
            arr.push_back(sure[which][i]);
            arr.push_back(counter + i);
        }
 
        int curr = use_machine(arr);
        
        sure[(which ^ (curr % 2))].push_back(counter + siz - 1);
        res += (which == 0 ? siz - curr / 2 - 1 : curr/2);
 
        //quick_update();
        which = (sure[0].size() >= sure[1].size() ? 0 : 1);
        counter += siz;
    }
    res += (int)sure[0].size();
}

int count_mushrooms(int n)
{
    // corner case
    if (n == 2){
        vector <int> arr = {0, 1};
        int curr = use_machine(arr);
        if (curr == 0)
            curr = 2;
        return curr;
    }
    
    sure[0].push_back(0);

    if (n < 20)
        first_two();
    else{
        phase1_1(min(n/2 - 5, maxk));
        phase1_2(min(n/2 - 5, maxk));
    }
    phase2(n);
    return res;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	200 KB	Output is correct
6	Correct	2 ms	200 KB	Output is correct
7	Correct	5 ms	200 KB	Output is correct
8	Correct	4 ms	296 KB	Output is correct
9	Correct	5 ms	200 KB	Output is correct
10	Correct	7 ms	200 KB	Output is correct
11	Correct	6 ms	200 KB	Output is correct
12	Correct	6 ms	200 KB	Output is correct
13	Correct	6 ms	200 KB	Output is correct
14	Correct	5 ms	200 KB	Output is correct
15	Correct	6 ms	200 KB	Output is correct
16	Correct	7 ms	328 KB	Output is correct
17	Correct	3 ms	200 KB	Output is correct
18	Correct	6 ms	292 KB	Output is correct
19	Correct	6 ms	304 KB	Output is correct
20	Correct	6 ms	200 KB	Output is correct
21	Correct	5 ms	300 KB	Output is correct
22	Correct	6 ms	200 KB	Output is correct
23	Correct	5 ms	304 KB	Output is correct
24	Correct	5 ms	200 KB	Output is correct
25	Correct	7 ms	200 KB	Output is correct
26	Correct	6 ms	304 KB	Output is correct
27	Correct	7 ms	200 KB	Output is correct
28	Correct	7 ms	200 KB	Output is correct
29	Correct	6 ms	200 KB	Output is correct
30	Correct	5 ms	200 KB	Output is correct
31	Correct	8 ms	292 KB	Output is correct
32	Correct	6 ms	200 KB	Output is correct
33	Correct	6 ms	200 KB	Output is correct
34	Correct	6 ms	200 KB	Output is correct
35	Correct	6 ms	200 KB	Output is correct
36	Correct	8 ms	200 KB	Output is correct
37	Correct	6 ms	308 KB	Output is correct
38	Correct	8 ms	200 KB	Output is correct
39	Correct	5 ms	200 KB	Output is correct
40	Correct	8 ms	296 KB	Output is correct
41	Correct	7 ms	300 KB	Output is correct
42	Correct	6 ms	200 KB	Output is correct
43	Correct	6 ms	304 KB	Output is correct
44	Correct	6 ms	200 KB	Output is correct
45	Correct	7 ms	200 KB	Output is correct
46	Correct	6 ms	200 KB	Output is correct
47	Correct	5 ms	200 KB	Output is correct
48	Correct	6 ms	300 KB	Output is correct
49	Correct	6 ms	200 KB	Output is correct
50	Correct	8 ms	300 KB	Output is correct
51	Correct	6 ms	300 KB	Output is correct
52	Correct	6 ms	308 KB	Output is correct
53	Correct	6 ms	200 KB	Output is correct
54	Correct	6 ms	292 KB	Output is correct
55	Correct	6 ms	200 KB	Output is correct
56	Correct	7 ms	200 KB	Output is correct
57	Correct	6 ms	200 KB	Output is correct
58	Correct	6 ms	200 KB	Output is correct
59	Correct	7 ms	200 KB	Output is correct
60	Correct	6 ms	200 KB	Output is correct
61	Correct	6 ms	200 KB	Output is correct
62	Correct	0 ms	200 KB	Output is correct
63	Correct	0 ms	200 KB	Output is correct
64	Correct	0 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	0 ms	200 KB	Output is correct
68	Correct	0 ms	200 KB	Output is correct
69	Correct	0 ms	200 KB	Output is correct
70	Correct	0 ms	200 KB	Output is correct
71	Correct	0 ms	272 KB	Output is correct
72	Correct	0 ms	200 KB	Output is correct
73	Correct	0 ms	200 KB	Output is correct
74	Correct	0 ms	200 KB	Output is correct
75	Correct	0 ms	200 KB	Output is correct
76	Correct	1 ms	200 KB	Output is correct
77	Correct	0 ms	200 KB	Output is correct
78	Correct	0 ms	200 KB	Output is correct
79	Correct	1 ms	200 KB	Output is correct
80	Correct	0 ms	200 KB	Output is correct
81	Correct	0 ms	200 KB	Output is correct
82	Correct	1 ms	200 KB	Output is correct
83	Correct	0 ms	200 KB	Output is correct
84	Correct	0 ms	200 KB	Output is correct
85	Correct	1 ms	200 KB	Output is correct
86	Correct	0 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	0 ms	200 KB	Output is correct