Submission #837128

#	Time	Username	Problem	Language	Result	Execution time	Memory
837128		azatega	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	256 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-1){
        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){
            known_as.push_back(new_idx);
        }else{
            known_bs.push_back(new_idx);
        }
 
        // each one causes two A.A.A
        res += rs/2; // bs counted total
        idx = new_idx;
    }
 
    if(swapped)
        return known_bs.size() + res;
    return known_as.size() + (n - known_as.size() - known_bs.size() - res);
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:67:9: warning: unused variable 'res2' [-Wunused-variable]
   67 |     int res2 = 0;
      |         ^~~~

• Subtask 1: 0 / 100