Submission #335396

#	Time	Username	Problem	Language	Result	Execution time	Memory
335396		rocks03	Counting Mushrooms (IOI20_mushrooms)	C++14	61.25 / 100	13 ms	620 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;
    for(int i = 1; i < n; i++){
        if(SZ(a) >= 100 || SZ(b) >= 100){
            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);
                    }
                }
            }
            break;
        }
        int res = use_machine({0, i});
        if(res == 0){
            a.pb(i);
            ++ans;
        } else if(res == 1){
            b.pb(i);
        }
    }
	return ans;
}

• Subtask 1: 61.2466 / 100