Submission #408875

#	Time	Username	Problem	Language	Result	Execution time	Memory
408875		AmineTrabelsi	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	1 ms	200 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;
    assert(known.size() > 0);
    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);
            if(type){
                ans += (cnt/2) + (cnt&1);
            }else{
                ans += ((int)m.size()/2) - (cnt/2) + (cnt&1);
            }
            if(!(cnt&1)){
                known.push_back(m.back());
            }
            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

AAAA 0
AAAB 1
ABAA 2
ABAB 3

*/

• Subtask 1: 0 / 100