Submission #1238682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238682		moondarkside	Counting Mushrooms (IOI20_mushrooms)	C++20	92.62 / 100	3 ms	464 KiB

mushrooms

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


int use_machine(vector<int> x);






int count_mushrooms(int n){
    int checked=2;
    if(n==2){
        return 2-use_machine(vector<int>{0,1});
    }
    
    vector<int> A={0};
    vector<int> B;
    
    if(use_machine(vector<int>{0,1})==0){
        A.push_back(1);
    }
    else{
        checked=3;
        B.push_back(1);
        if(use_machine(vector<int>{0,2})==0){
            A.push_back(2);
        }
        else{
            B.push_back(2);
        }
    }
    
    
    if (n<232){
        
        for(int i=checked;i<n;i++){
            if(use_machine(vector<int>{0,i})==0){
                A.push_back(i);
            }
        }
        return A.size();
    }
    
    
    for(;A.size()<80 && B.size()<80;checked+=2){
        if(A.size()>1){
            int val=use_machine(vector<int>{A[0],checked,A[1],checked+1});
            if(val%2==0){
                A.push_back(checked+1);
            }
            else{
                B.push_back(checked+1);
            }
            
            if(val>1){
                B.push_back(checked);
            }
            else{
                A.push_back(checked);
            }
            
        }
        else{
            int val=use_machine(vector<int>{B[0],checked,B[1],checked+1});
            
            if(val%2==0){
                B.push_back(checked+1);
            }
            else{
                A.push_back(checked+1);
            }
            
            if(val>1){
                A.push_back(checked);
            }
            else{
                B.push_back(checked);
            }
            
        }
    }
    
        
        
        
        int value=A.size();
        bool running=true;
        
        while(running){
            bool inverse=false;
            vector<int> Calc=A;
            if(B.size()>A.size()){
                Calc=B;
                inverse=true;
            }
            
            vector<int> Question;
            int inv=0;
            
            for(int i=0;i<Calc.size();i++){
                if(checked==n){
                    running=false;
                }
                else{
                    inv++;
                    Question.push_back(checked);
                    checked++;
                }
                Question.push_back(Calc[i]);
            }
            
            int val=use_machine(Question);
            if(val%2==1){
                if(inverse){
                    A.push_back(Question[0]);
                }
                else{
                    B.push_back(Question[0]);
                }
                val++;
            }
            else{
                if(!inverse){
                    A.push_back(Question[0]);
                }
                else{
                    B.push_back(Question[0]);
                }
            }
            val=val/2;
            
            if(!inverse){
                val=inv-val;
            }
            
            value+=val;
        }
        
        
        
        return value;
        
}

• Subtask 1: 92.623 / 100