Submission #408915

#	Time	Username	Problem	Language	Result	Execution time	Memory
408915		AmineTrabelsi	Counting Mushrooms (IOI20_mushrooms)	C++14	25 / 100	18 ms	420 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 70;
int small(int n){
    vector<int> m;
    int ans = 1;
    for (int i = 1; i < n; i++)
        ans += (use_machine({0,i}) == 0);
    return ans;
}
int count_mushrooms(int n) {
    if(n <= 200){
        return small(n);
    }
    bool type = 0;
    vector<int> known,known_A,known_B;
    int ind = 3;
    int ans = 1;
    // part one
    bool sec = use_machine({0,1});
    bool th = use_machine({0,2});
    ans += (sec == 0) + (th == 0);
    known_A.push_back(0);
    if(sec == 0)known_A.push_back(1);
    else known_B.push_back(1);
    if(th == 0)known_A.push_back(2);
    else known_B.push_back(2);
    while(ind < n && known_A.size() < K && known_B.size() < K){
        if(use_machine({0,ind}) == 0){
            ans++;
            known_A.push_back(ind);
        }else{
            known_B.push_back(ind);
        }
        ind++;
    }
    if(known_A >= known_B){
        type = 0;
        known = known_A;
    }else{
        type = 1;
        known = known_B;
    }
    // part two
    vector<int> m;
    int i = 0;
    while(ind < n){
        if(i < (int)known.size()){
            m.push_back(known[i]);
            m.push_back(ind);
            ind++;
            i++;
        }
        if(i == (int)known.size() || ind == n){
            int cnt = use_machine(m);
            int elem = m.size();
            if(!(cnt&1)){
                known.push_back(m.back());
                if(type == 0)ans++;
            }else if(type)ans++;
            cnt -= cnt&1;
            elem-=2;
            int kn = elem/2;
            if(type){
                ans += cnt/2;
            }else ans += kn-(cnt/2);
            m.clear();
            i = 0;
        }
    }
    return ans;
}
/*
21
0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

_ = A

_A 0 
_B 1
_A_A 0
_A_B 1
_B_A 2
_B_B 3

_ = B
_A = 1
_B = 0
_B_B 0
_B_A 1
_A_B 2
_A_A 3
*/

• Subtask 1: 25 / 100