답안 #837114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837114	2023-08-25T00:51:25 Z	azatega	버섯 세기 (IOI20_mushrooms)	C++17	0 / 100	0 ms	208 KB

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_bs.size() == 2){
       known_as.swap(known_bs);
       swapped = true;
    } // a is b b is a

    while(known_as.size() < 137 && known_bs.size() < 137 && idx + 1 <= 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()){
        known_as.swap(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, (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.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	208 KB	Too large array for query.
2	Halted	0 ms	0 KB	-