Submission #1240321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240321		Ghulam_Junaid	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	632 KiB

mushrooms

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

mt19937 rng(678147511);

int count_mushrooms(int n) {
	vector<int> a, b, order;
    a.push_back(0);
    for (int i = 1; i < n; i ++)
        order.push_back(i);
    shuffle(order.begin(), order.end(), rng);

    int ans = 1;
    while (order.size()){
        if (a.size() > b.size()){
            vector<int> vec;
            int sz = min(a.size(), order.size());
            for (int i = 0; i < sz; i ++){
                vec.push_back(order.back());
                vec.push_back(a[i]);
                order.pop_back();
            }

            int val = use_machine(vec);
            if (val % 2)
                b.push_back(vec[0]);
            else
                a.push_back(vec[0]);
            ans += sz - (val + 1) / 2;
        }
        else{
            vector<int> vec;
            int sz = min(b.size(), order.size());
            for (int i = 0; i < sz; i ++){
                vec.push_back(order.back());
                vec.push_back(b[i]);
                order.pop_back();
            }

            int val = use_machine(vec);
            if (val % 2)
                a.push_back(vec[0]);
            else
                b.push_back(vec[0]);
            ans += (val + 1) / 2;
        }
    }
    return ans;
}

• Subtask 1: 80.7143 / 100