Submission #1247070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247070		nikulid	Counting Mushrooms (IOI20_mushrooms)	C++20	68.69 / 100	3 ms	432 KiB

mushrooms

#include <iostream>
#include "mushrooms.h"

bool debug=0;
using namespace std;

#define pb push_back

int count_mushrooms(int n) {
    vector<int> m = {0};
    if(n<100){
        int smallans=1;
        for(int i=1; i<n; i++){
            m = {0, i};
            smallans += (1-use_machine(m));
        }
        return smallans;
    }

    int answer;
    int cnt0=1, cnt1=0;

    vector<int> ones, zeros={0};
    vector<bool> known(n+1, 0);
    known[0]=1;

    int val;
    for(int i=1; i<min(300, n-1); i+=2){
        m.pb(i);
        m.pb(i+1);
        val = use_machine(m);
        if(val==0){
            // {0,0,0}
            cnt0+=2;
            zeros.pb(i);
            zeros.pb(i+1);
            known[i]=1;
            known[i+1]=1;
        } else if(val==1){
            // {0,_,1}
            cnt1++;
            ones.pb(i+1);
            known[i+1]=1;
        } else if(val==2){
            // {0,1,0}
            cnt0++;cnt1++;
            zeros.pb(i+1);
            ones.pb(i);
            known[i]=1;
            known[i+1]=1;
        }
        m = {0};
    }
    if(debug)
    {
        cout<<"$ known: ";
        for(int i=0; i<n; i++){
            cout<<known[i]<<" ";
        }cout<<"\n";

    }
    int next_unknown = 1;
    while(known[next_unknown])next_unknown++;
    if(cnt0 >= cnt1){
        answer = n-cnt1;
        while(next_unknown < n){
            m = {zeros[0]};
            for(int i=1; i<cnt0; i++){
                if(next_unknown >= n)break;
                m.pb(next_unknown);
                m.pb(zeros[i]);
                known[next_unknown]=true;
                while(known[next_unknown])next_unknown++;
            }
            answer -= use_machine(m)/2;
        }
        return answer;
    } else{
        answer = cnt0;
        while(next_unknown < n){
            m = {ones[0]};
            for(int i=1; i<cnt1; i++){
                if(next_unknown >= n)break;
                m.pb(next_unknown);
                m.pb(ones[i]);
                known[next_unknown]=true;
                while(known[next_unknown])next_unknown++;
            }
            answer += use_machine(m)/2;
        }
        return answer;
    }
}

• Subtask 1: 68.693 / 100