Submission #309758

#	Time	Username	Problem	Language	Result	Execution time	Memory
309758		georgerapeanu	Counting Mushrooms (IOI20_mushrooms)	C++17	87.94 / 100	10 ms	640 KiB

mushrooms

#include "mushrooms.h"
#include <cstdio>
#include <chrono>
#include <algorithm>
#include <random>

using namespace std;

const int TARGET = 141;

int count_mushrooms(int n) {

    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

    vector<int> stuff[2];
    stuff[0] = {0};

    vector<int> order;

    for(int i = 1;i < n;i++){
        order.push_back(i);
    }

    shuffle(order.begin(),order.end(),gen);

    if(n <= 226){
        int ans = 1;
        for(int i = 1;i < n;i++){
            ans += (use_machine({0,i}) == 0);
        }
        return ans;
    }

    for(int i = 0;stuff[0].size() < 2 && stuff[1].size() < 2;i++){
        stuff[use_machine({0,order.back()})].push_back(order.back());
        order.pop_back();
    }

    while((int)stuff[0].size() < TARGET && (int)stuff[1].size() < TARGET && (int)order.size() > 1){
        if((int)stuff[0].size() > 1){
            int a = order.back();order.pop_back();
            int b = order.back();order.pop_back();
            int tmp = use_machine({stuff[0][0],a,stuff[0][1],b});
            stuff[tmp % 2].push_back(b);
            stuff[tmp / 2].push_back(a);
        }
        else{
            int a = order.back();order.pop_back();
            int b = order.back();order.pop_back();
            int tmp = use_machine({stuff[1][0],a,stuff[1][1],b});
            stuff[1 - (tmp % 2)].push_back(b);
            stuff[1 - (tmp / 2)].push_back(a);
        }
    }

    if(order.size() == 1){
        return (int)stuff[0].size() + (use_machine({0,order[0]}) == 0);
    }

    if(order.size() == 0){
        return stuff[0].size();
    }

    int ans = stuff[0].size();

    while((int)order.size() > 0){
        int cnt = min(order.size(),max(stuff[0].size(),stuff[1].size()));
        vector<int> tmp;
        if(stuff[0].size() > stuff[1].size()){
            for(int i = 0;i < cnt;i++){
                tmp.push_back(stuff[0][i]);
                tmp.push_back(order[(int)order.size() - 1 - i]);
            }
            int aux = use_machine(tmp);
            ans += cnt - ((aux / 2) + (aux % 2));
            stuff[aux % 2].push_back(tmp.back());
        }
        else{
            for(int i = 0;i < cnt;i++){
                tmp.push_back(stuff[1][i]);
                tmp.push_back(order[(int)order.size() - 1 - i]);
            }
            int aux = use_machine(tmp);
            ans += ((aux / 2) + (aux % 2));
            stuff[1 - (aux % 2)].push_back(tmp.back());
        }
        for(int i = 0;i < cnt;i++){
            order.pop_back();
        }
    }

    return ans;
}

• Subtask 1: 87.9377 / 100