Submission #1058187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058187		idas	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	6 ms	696 KiB

mushrooms

#include "mushrooms.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back

using namespace std;
typedef vector<int> vi;

const int MxN=2e4, C=142;
int n;
vi a, b;

int count_mushrooms(int N) {
    n=N; a.pb(0);

    if(use_machine({0,1})) b.pb(1);
    else a.pb(1);

    if(n==2) return sz(a);

    if(use_machine({0,2})) b.pb(2);
    else a.pb(2);

    int in=3;
    while(in<=n-2 && sz(a)<C && sz(b)<C) {
        if(sz(a)>=2) {
            int k=use_machine({a[0], in, a[1], in+1});
            if(k==0) a.pb(in), a.pb(in+1);
            else if(k==1) a.pb(in), b.pb(in+1);
            else if(k==2) b.pb(in), a.pb(in+1);
            else b.pb(in), b.pb(in+1);
            in+=2;
        }
        else {
            int k=use_machine({b[0], in, b[1], in+1});
            if(k==0) b.pb(in), b.pb(in+1);
            else if(k==1) b.pb(in), a.pb(in+1);
            else if(k==2) a.pb(in), b.pb(in+1);
            else a.pb(in), a.pb(in+1);
            in+=2;
        }
    }

    int ans=sz(a);
    if(sz(a)>=sz(b)) {
        while(in<n) {
            vi tmp; int actual=0;
            FOR(i, 0, sz(a)) {
                tmp.pb(a[i]);
                if(in<n) tmp.pb(in++), actual++;
            }
            int k=use_machine(tmp);

            // cout << "query: ";
            // for(auto it : tmp) {
            //     cout << it << " ";
            // }
            // cout << endl << k << endl;

            ans+=actual-(k+1)/2;
        }
    }
    else {
        while(in<n) {
            vi tmp;
            FOR(i, 0, sz(b)) {
                tmp.pb(b[i]);
                if(in<n) tmp.pb(in++);
            }
            int k=use_machine(tmp);
            ans+=(k+1)/2;
        }
    }

    return ans;
}
/*
3
0 1 0

10
0 0 0 0 0 0 0 0 0 0
*/

• Subtask 1: 80.427 / 100