Submission #531686

#	Time	Username	Problem	Language	Result	Execution time	Memory
531686		EqualTurtle	Counting Mushrooms (IOI20_mushrooms)	C++14	99.56 / 100	10 ms	436 KiB

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 = 95;
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
    {
        //vector <int> arr = {zero1, A, B, C, D, zero2, E};
        int curr = use_machine({zero1, A, B, C, D, zero2, E});

        if (curr == 0)
            assign({0, 0, 0, 0, 0}, A);
        else{
            assign({curr % 2}, E);
            curr = use_machine({zero1, A, zero2, B});
            assign({curr / 2, curr % 2}, A);
            curr = use_machine({zero1, C, zero2, D});
            assign({curr / 2, curr % 2}, C);
        }

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

    first_two();
    phase1_1(min(n/2 - 5, maxk));
    phase1_2(min(n/2 - 5, maxk));
    phase2(n);
    return res;
}

• Subtask 1: 99.5595 / 100