Submission #586689

#	Time	Username	Problem	Language	Result	Execution time	Memory
586689		PiejanVDC	Counting Mushrooms (IOI20_mushrooms)	C++17	66.86 / 100	12 ms	336 KiB

mushrooms

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

int use_machine(vector<int> x);

const int g = 90;

int count_mushrooms(int n) {
    int A = 1, B = 0;
    vector<int>a,b;
    a.push_back(0);
    int p = 1;
    while(A < g && B < g) {
        if(p == n)
            return A;
        if(!use_machine({0, p}))
            A++, a.push_back(p);
        else
            B++, b.push_back(p);
        p++;
    }
    while(A + B < n) {
        if(a.size() > b.size()) {
            int lim = min((int)a.size(), n-p);
            vector<int>ask;
            for(int i = 0 ; i < lim ; i++) {
                ask.push_back(a[i]);
                ask.push_back(p);
                p++;
            }
            int x = use_machine(ask);
            x++;
            B += x/2;
            if(x&1)
                a.push_back(p-1);
            A += lim - x/2;
        } else {
            int lim = min((int)b.size(), n-p);
            vector<int>ask;
            for(int i = 0 ; i < lim ; i++) {
                ask.push_back(b[i]);
                ask.push_back(p);
                p++;
            }
            int x = use_machine(ask);
            x++;
            A += x/2;
            if(x&1)
                b.push_back(p-1);
            B += lim - x/2;
        }
    }
    return A;
}

• Subtask 1: 66.8639 / 100