Submission #1248070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248070		nikulid	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	0 ms	428 KiB

mushrooms

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

using namespace std;

bool debug=0;
#define dout if(debug)cout

#define pb push_back
#define mp make_pair

int count_mushrooms(int n) {
    vector<int> m = {0};
    if(n<200){
        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+2, 0);
    known[0]=1;

    int val;
    
    pair<int, int> zs;
    // spend 2 queries finding atleast a 2nd instance of 1, or 2 instances of 0:

    known[1]=1;
    bool usingzeros;
    m={0,1};
    if(use_machine(m)){
        // {0,1}
        cnt1++;
        ones.pb(1);
        known[2]=1;
        m={0,2};
        if(use_machine(m)){
            // {0,1,1}
            cnt1++;
            ones.pb(2);
            zs = mp(1,2);
            usingzeros = false; 
        } else{
            // {0,1,0}
            cnt0++;
            zeros.pb(2);
            zs = mp(0,2);
            usingzeros = true;
        }
    } else{
        cnt0++;
        zeros.pb(1);
        zs = mp(0,1);
        usingzeros = true;
    }

    // querying {1,x,1,y} tells us all about x and y. 
    // doing this 100 times is pretty nice
   
    dout<<"finished the first 2 queries. we have the pair ("<<zs.first<<","<<zs.second<<").\n";

    int a=1,b=1;
    for(int j=0; j<min(98, n/3); j++){
        while(known[a]) a++;
        known[a]=1;
        while(known[b]) b++;
        known[b]=1;
        m={zs.first, a, zs.second, b};
        val = use_machine(m);
        if(val==0){
            // ns[a]=ns[b]=zs
            if(usingzeros){
                cnt0+=2;
                zeros.pb(a);
                zeros.pb(b);
            } else{
                cnt1+=2;
                ones.pb(a);
                ones.pb(b);
            }
        } else if(val==1){
            
            cnt0++;
            cnt1++;
            if(usingzeros){
                ones.pb(a);
                zeros.pb(b);
            } else{
                ones.pb(b);
                zeros.pb(a);
            }
        } else if(val==2){
            // a is the same as usingzeros
            cnt0++;
            cnt1++;
            if(usingzeros){
                zeros.pb(a);
                ones.pb(b);
            } else{
                ones.pb(a);
                zeros.pb(b);
            }
        } else{ 
            // a==b==!zs
            if(usingzeros){
                cnt1+=2;
                ones.pb(a);
                ones.pb(b);
            } else{
                cnt0+=2;
                zeros.pb(a);
                zeros.pb(b);
            }
        }
    }


    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.resize(0);
            for(int i=0; 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)+1)/2;
        }
        return answer;
    } else{
        answer = cnt0;
        while(next_unknown < n){
            m.resize(0);
            for(int i=0; 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)+1)/2;
        }
        return answer;
    }
}

• Subtask 1: 0 / 100