Submission #586662

#	Time	Username	Problem	Language	Result	Execution time	Memory
586662		PiejanVDC	Counting Mushrooms (IOI20_mushrooms)	C++17	27.26 / 100	12 ms	472 KiB

mushrooms

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

int use_machine(vector<int> x);


int count_mushrooms(int n) {
    int A = 1, B = 0;
    vector<int>a,b;
    a.push_back(0);
    int p = 1;
    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: 27.2618 / 100