Submission #837117

#	Time	Username	Problem	Language	Result	Execution time	Memory
837117		azatega	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	0 ms	208 KiB

mushrooms

#include <iostream>
#include <vector>

using namespace std;

int use_machine(vector<int> l);

int count_mushrooms(int n){
    vector<int> known_as;
    vector<int> known_bs;

    if(n == 1)
        return 1;

    if(n == 2){
        vector<int> use = {0, 1};
        int rs = use_machine(use);
        if(rs == 1)
            return 1;
        else
            return 2;
    }

    known_as.push_back(0);

    int idx = 0; // index tested

    while(known_as.size() < 2 && known_bs.size() < 2){
        vector<int> use = {0, idx+1};
        int rs = use_machine(use);
        if(rs == 0)
            known_as.push_back(idx+1);
        else if(rs == 1)
            known_bs.push_back(idx+1);
        idx++;
    }

    bool swapped = false;
    if(known_as.size() < known_bs.size()){
       swap(known_as, known_bs);
       swapped = true;
    } // a is b b is a

    while(known_as.size() < 135 && known_bs.size() < 135 && idx + 2 < n){
        vector<int> use = {known_as[0], idx+1, known_as[1], idx+2};
        int rs = use_machine(use);
        if(rs == 0){
            // both as
            known_as.push_back(idx+1);
            known_as.push_back(idx+2);
        }else if(rs == 1){
            known_as.push_back(idx+1);
            known_bs.push_back(idx+2);
        }else{
            known_bs.push_back(idx+1);
            known_bs.push_back(idx+2);
        }
        idx += 2;
    }

    if(known_as.size() < known_bs.size()){
        swap(known_as, known_bs);
        swapped = !swapped;
    }

    int res = 0;
    int res2 = 0;

    while(idx < n){
        vector<int> use;
        int new_idx = idx;
        for(int t = 1; t <= min(n-idx-1, (int)known_as.size()); t++){
            use.push_back(known_as[t-1]);
            use.push_back(idx+t);
            new_idx=idx+t;
        }
        int rs = use_machine(use);
        if(rs % 2 != 0)
            rs++;
        rs /= 2;
        res += rs;
        res2 += (new_idx-idx - rs);
        idx = new_idx;
    }

    if(swapped)
        return known_bs.size() + res2;
    return known_as.size() + res;
}

• Subtask 1: 0 / 100