Submission #657881

#	Time	Username	Problem	Language	Result	Execution time	Memory
657881		mychecksedad	Counting Mushrooms (IOI20_mushrooms)	C++17	80.14 / 100	13 ms	336 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
 
 
int use_machine(std::vector<int> x);
int count_mushrooms(int n) {
    int ans = 0;
    if(n <= 200){
        for(int i = 1; i < n; ++i){
            vector<int> v {0, i};
            ans += 1 - use_machine(v);
        }
        return ans + 1;
    }
    vector<int> a {0}, b; //specific zeros and ones
    int S = 282, K = 0;
    for(int i = 1; i < min(S + 2, n); i++){
        vector<int> v {0, i};
        int val = use_machine(v);
        if(val==0){
            a.pb(i);
        }else{
            b.pb(i);
        }
        K = i;
        if(a.size() >= 2 || b.size() >= 2){
            break;
        }
    }
    for(int i = K + 1; i + 1 < min(S + 2, n); i += 2){
        if(a.size() >= 2){
            vector<int> v {a[0], i, a[1], i + 1};
            int val = use_machine(v);
            if(val == 0){
                a.pb(i);
                a.pb(i+1);
            }else if(val == 1){
                a.pb(i);
                b.pb(i+1);
            }else if(val == 2){
                b.pb(i);
                a.pb(i+1);
            }else{
                b.pb(i);
                b.pb(i+1);
            }
        }else{
            vector<int> v {b[0], i, b[1], i + 1};
            int val = use_machine(v);
            if(val == 0){
                b.pb(i);
                b.pb(i+1);
            }else if(val == 1){
                b.pb(i);
                a.pb(i+1);
            }else if(val == 2){
                a.pb(i);
                b.pb(i+1);
            }else{
                a.pb(i);
                a.pb(i+1);
            }
        }
        K = i + 1;
    }
    if(a.size() < b.size()){
        S = b.size();
        S--;
        for(int i = K + 1; i + S <= n; i += S){
            vector<int> v;
            int ind = 0;
            for(int j = i; j < i + S; ++j){
                v.pb(j), v.pb(b[ind++]);
                K = j;
            }
            int val = use_machine(v);
            ans += val/2 + (val%2);
        }
        if(K + 1 < n){
            vector<int> v;
            int ind = 0;
            for(int j = K + 1; j < n; ++j){
                v.pb(j), v.pb(b[ind++]);
            }
            int val = use_machine(v);
            ans += val/2 + (val%2);
        }
    }else{
        S = a.size();
        S--;
        // cout << S <<"S" << K << endl;;
        for(int i = K + 1; i + S <= n; i += S){
            vector<int> v;
            int ind = 0;
            for(int j = i; j < i + S; ++j){
                v.pb(j), v.pb(a[ind++]);
                K = j;
            }
            int val = use_machine(v);
            ans += v.size()/2 - val/2 - (val%2);
        }
        if(K + 1 < n){
            vector<int> v;
            int ind = 0;
            for(int j = K + 1; j < n; ++j){
                v.pb(j), v.pb(a[ind++]);
            }
            int val = use_machine(v);
            ans += v.size()/2 - val/2 - (val%2);
        }
    }
 
 
    return ans + a.size();
}
 

• Subtask 1: 80.1418 / 100