Submission #586069

#	Time	Username	Problem	Language	Result	Execution time	Memory
586069		Valaki2	Counting Mushrooms (IOI20_mushrooms)	C++14	91.87 / 100	9 ms	436 KiB

mushrooms

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

#define pb push_back

const int block = 101;

int init(vector<int> &a, vector<int> &b) {
    a.pb(0);
    vector<int> v = {0, 1};
    if(use_machine(v)) {
        b.pb(1);
    } else {
        a.pb(1);
    }
    v = {0, 2};
    if(use_machine(v)) {
        b.pb(2);
    } else {
        a.pb(2);
    }
    return 3;
}

int count_mushrooms(int n) {
    if(n == 2) {
        vector<int> v = {0, 1};
        return 2 - use_machine(v);
    }
    vector<int> a;
    vector<int> b;
    int idx = init(a, b);
    for(int i = 0; i < min(block, n / 2); i++) {
        if(idx == n) {
            break;
        }
        if(idx == n - 1) {
            vector<int> v = {0, idx};
            if(use_machine(v)) {
                b.pb(idx);
            } else {
                a.pb(idx);
            }
            idx++;
            break;
        }
        vector<int> v;
        if((int) a.size() >= 2) {
            v = {a[0], idx, a[1], idx + 1};
            int tmp = use_machine(v);
            if(tmp & 2) {
                b.pb(idx);
            } else {
                a.pb(idx);
            }
            if(tmp & 1) {
                b.pb(idx + 1);
            } else {
                a.pb(idx + 1);
            }
        } else {
            v = {b[0], idx, b[1], idx + 1};
            int tmp = use_machine(v);
            if(tmp & 2) {
                a.pb(idx);
            } else {
                b.pb(idx);
            }
            if(tmp & 1) {
                a.pb(idx + 1);
            } else {
                b.pb(idx + 1);
            }
        }
        idx += 2;
    }
    int ans = 0;
    while(idx < n) {
        bool use_b = false;
        int l = a.size();
        if(b.size() > a.size()) {
            use_b = true;
            l = b.size();
        }
        l = min(l, n - idx);
        int cnt = 0;
        vector<int> v;
        while(cnt < l) {
            if(use_b) {
                v.pb(b[cnt]);
            } else {
                v.pb(a[cnt]);
            }
            v.pb(idx);
            idx++;
            cnt++;
        }
        int tmp = use_machine(v);
        if(!use_b) {
            ans += l - (tmp / 2 + tmp % 2);
            if(tmp % 2) {
                b.pb(idx - 1);
            } else {
                a.pb(idx - 1);
                ans--;
            }
        } else {
            ans += (tmp / 2 + tmp % 2);
            if(tmp % 2) {
                a.pb(idx - 1);
                ans--;
            } else {
                b.pb(idx - 1);
            }
        }
    }
    return ans + (int) a.size();
}

• Subtask 1: 91.8699 / 100