Submission #408900

#	Time	Username	Problem	Language	Result	Execution time	Memory
408900		AmineTrabelsi	Counting Mushrooms (IOI20_mushrooms)	C++14	27.26 / 100	16 ms	452 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 100;
/*
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 if A 1 if B
    vector<int> known;
    int ind = 1;
    int ans = 1;
    // part one
    type = 0;
    known.push_back(0);
    // 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){/*
            for(auto x:m)cerr<<x<<" ";
                cerr<<'\n';*/
            int cnt = use_machine(m);
            //cerr<<cnt<<'\n';
            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;
            //cerr<<ans<<'\n';
        }
    }
    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: 27.2618 / 100