Submission #335397

#	Time	Username	Problem	Language	Result	Execution time	Memory
335397		rocks03	Counting Mushrooms (IOI20_mushrooms)	C++14	25 / 100	129 ms	492 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int use_machine(vector<int> x);

int count_mushrooms(int n){
    vector<int> a, b;
    a.pb(0);
    int ans = 1, i = 1;
    while(1){
        if(i >= n) break;
        if(SZ(a) > SZ(b)){
            vector<int> v;
            int j = i;
            while(j < n && j < i + SZ(a)){
                v.pb(a[j - i]);
                v.pb(j);
                j++;
            }
            int res = use_machine(v);
            ans += SZ(v) / 2 - (res + 1) / 2;
            i = j;
            if(res&1){
                b.pb(i - 1);
            }
        } else{
            vector<int> v;    
            int j = i;
            while(j < n && j < i + SZ(b)){
                v.pb(b[j - i]);
                v.pb(j);
                j++;
            }
            int res = use_machine(v);
            ans += (res + 1) / 2;
            i = j;
            if(res&1){
                a.pb(i - 1);
            }
        }
    }
	return ans;
}

• Subtask 1: 25 / 100