Submission #1240325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240325		Ghulam_Junaid	Counting Mushrooms (IOI20_mushrooms)	C++20	81 / 100	4 ms	648 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]);
                if (val == 2 * (sz - 1) + 1)
                    for (int i = 2; i < vec.size(); i += 2)
                        b.push_back(vec[i]);
                if (val == 1)
                    for (int i = 2; i < vec.size(); i += 2)
                        a.push_back(vec[i]);
            }
            else{
                a.push_back(vec[0]);
                if (val == 2 * (sz - 1))
                    for (int i = 2; i < vec.size(); i += 2)
                        b.push_back(vec[i]);
                if (val == 0)
                    for (int i = 2; i < vec.size(); i += 2)
                        a.push_back(vec[i]);
            }
            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]);
                if (val == 2 * (sz - 1) + 1)
                    for (int i = 2; i < vec.size(); i += 2)
                        a.push_back(vec[i]);
                if (val == 1)
                    for (int i = 2; i < vec.size(); i += 2)
                        b.push_back(vec[i]);
            }
            else{
                b.push_back(vec[0]);
                if (val == 2 * (sz - 1))
                    for (int i = 2; i < vec.size(); i += 2)
                        a.push_back(vec[i]);
                if (val == 0)
                    for (int i = 2; i < vec.size(); i += 2)
                        b.push_back(vec[i]);
            }
            ans += (val + 1) / 2;
        }
    }
    return ans;
}

• Subtask 1: 81.0036 / 100