제출 #1247057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247057		nikulid	버섯 세기 (IOI20_mushrooms)	C++20	0 / 100	0 ms	404 KiB

mushrooms

#include "mushrooms.h"

using namespace std;

#define pb push_back

int count_mushrooms(int n) {
    int answer;
    int cnt0=1, cnt1=0;

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

    int val;
    vector<int> m = {0};
    for(int i=1; i<min(300, n); 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);
            ones.pb(i+1);
            known[i]=1;
            known[i+1]=1;
        }
        m = {0};
    }
    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: 0 / 100