Submission #529824

#	Time	Username	Problem	Language	Result	Execution time	Memory
529824		EqualTurtle	Counting Mushrooms (IOI20_mushrooms)	C++14	92.24 / 100	8 ms	312 KiB

mushrooms

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

constexpr int maxk = 100;

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

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;
    arr.push_back(0);
    arr.push_back(1);
    int curr = use_machine(arr);

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

    sure[1].push_back(1);
    arr.pop_back();
    arr.push_back(2);
    curr = use_machine(arr);

    sure[curr].push_back(2);

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

void phase1(int k)
{
    vector<int> arr = {0, 0, 0, 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);

        counter += 2;
    }
}

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

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

        which = (sure[0].size() >= sure[1].size() ? 0 : 1);

        //while (arr.size()) arr.pop_back();
        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();
    // already know at least 2 of same kind
    //debug();
    phase1(min(n/2 - 1, maxk));
    //debug();
    // already know at leat k of same kind
    phase2(n);
    //debug();

    return res;
}

/*
10
0 0 0 0 0 0 0 0 0 1
*/

• Subtask 1: 92.2449 / 100