Submission #1238468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238468		moondarkside	Counting Mushrooms (IOI20_mushrooms)	C++20	77.93 / 100	3 ms	428 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<226){
        
        for(int i=checked;i<n;i++){
            if(use_machine(vector<int>{0,i})==0){
                A.push_back(i);
            }
        }
        return A.size();
    }
    
    
    for(;checked<220;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);
            }
            
        }
    }
    
    //if(A.size()*3/2 > B.size() || B.size()*3/2 > A.size()){
        bool inverse=false;
        if(B.size()>A.size()){
            inverse=true;
            A=B;
        }
        
        int value=A.size();
        bool running=true;
        while(running){
            vector<int> Question;
            int inv=0;
            for(int i=0;i<A.size();i++){
                if(checked==n){
                    running=false;
                }
                else{
                    inv++;
                    Question.push_back(checked);
                    checked++;
                }
                Question.push_back(A[i]);
            }
            int val=use_machine(Question);
            if(val>0){
                val=((val-1)/2+1);
            
            }
            value+=inv-val;
        }
        
        if(inverse){
            value=n-value;
        }
        
        return value;
        
    //}
    
    
    
    
    
    
}

• Subtask 1: 77.931 / 100