Submission #1238680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238680		moondarkside	Counting Mushrooms (IOI20_mushrooms)	C++20	Compilation error	0 ms	0 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(;checked<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;
        
}

vector<int> Type;
int q=0;

int use_machine(vector<int> x){
    q++;
    int v=0;
    for(int i=1;i<x.size();i++){
        if(Type[x[i]]!=Type[x[i-1]]){
            v++;
        }
    }
    return v;
}


int main()
{
    for(int i=0;i<1000;i++){
        rand();
    }
    
    Type.push_back(0);
    for(int i=0;i<20001;i++){
        Type.push_back(rand()%2);
    }
    int v;
    for(int i=0;i<20000;i++){
        v+=1-Type[i];
    }
    cout<<v<<"\n";
    
    std::cout<<count_mushrooms(20000);
    
    cout<<" "<<q;

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccmeYnnP.o: in function `use_machine(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x150): multiple definition of `use_machine(std::vector<int, std::allocator<int> >)'; /tmp/cca5fHyd.o:mushrooms.cpp:(.text+0x0): first defined here
/usr/bin/ld: /tmp/ccmeYnnP.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cca5fHyd.o:mushrooms.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status