Submission #529306

#	Time	Username	Problem	Language	Result	Execution time	Memory
529306		EqualTurtle	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	1 ms	200 KiB

mushrooms

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

constexpr int maxk = 100;

vector <int> sure[2];
int res = 0;

//int use_machine(vector <int> arr);

void first_two()
{
    //int* arr = new int[2];
    //arr[0] = 0, arr[1] = 1;
    vector<int> arr;
    arr.push_back(0);
    arr.push_back(1);
    int curr = use_machine(arr);
    //delete[] arr;

    if (curr == 0){
        sure[0].push_back(1);
        return;
    }

    sure[1].push_back(1);
    //arr = new int[2];
    //arr[0] = 0, arr[1] = 2;
    arr.pop_back();
    arr.push_back(2);
    curr = use_machine(arr);
    //delete[] arr;

    sure[curr].push_back(2);

    while (arr.size())
        arr.pop_back();
}

void phase1(int k)
{
    //int* arr = new int[4];
    vector<int> arr = {0, 0, 0, 0};
    //arr.push_back(0);arr.push_back(0);arr.push_back(0);arr.push_back(0);
    int counter = (int)sure[0].size() + (int)sure[1].size();

    int which = (sure[0].size() >= 2 ? 0 : 1);
    while ((int)sure[0].size() < k && (int)sure[1].size() < k)
    {
        arr[0] = sure[which][0], arr[1] = counter, arr[2] = sure[which][1], arr[3] = counter + 1;
        int curr = use_machine(arr);

        sure[(which ^ (curr % 2))].push_back(counter + 1);
        curr /= 2;
        sure[(which ^ curr)].push_back(counter + 1);

        counter += 2;
    }
    //delete[] arr;
}

void phase2(int n)
{
    int counter = (int)sure[0].size() + (int)sure[1].size();
    int which = (sure[0].size() >= sure[1].size() ? 0 : 1);
    
    while (counter < n)
    {
        int siz = min(n - counter, (int)sure[which].size());

        //int* arr = new int[2 * siz];
        vector <int> arr;
        for (int i = 0; i < siz; i++){
            //arr[i * 2] = sure[which][i];
            //arr[i * 2 + 1] = counter + i;
            arr.push_back(sure[which][i]);
            arr.push_back(counter + i);
        }

        /*for (int i : arr)
            cout << i << " ";
        cout << "\n";*/
        int curr = use_machine(arr);
        
        sure[(which ^ (curr % 2))].push_back(counter + 1);
        res += (which == 0 ? curr / 2 : siz - curr/2);

        which = (sure[0].size() >= sure[1].size() ? 0 : 1);
        //delete[] arr;
        while (arr.size()) arr.pop_back();
        counter += siz;
    }
    res += (int)sure[0].size();
}

int count_mushrooms(int n)
{
    // very small n corner
    sure[0].push_back(0);

    first_two();
    // already know at least 2 of same kind
    phase1(min(n/2 - 1, maxk));
    // already know at leat k of same kind
    phase2(n);
    return res;
}

• Subtask 1: 0 / 100