Submission #352472

#	Time	Username	Problem	Language	Result	Execution time	Memory
352472		Osama_Alkhodairy	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	10 ms	532 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
//~ #include "stub.cpp"
using namespace std;

int count_mushrooms(int n){
    vector <int> p[2];
    p[0].push_back(0);
    for(int i = 1 ; i < min(n, 3) ; i++){
        int x = use_machine({0, i});
        p[x].push_back(i);
    }
    int idx = 3;
    int k = 90;
    while(idx + 1 < n && (int)max(p[0].size(), p[1].size()) < k){
        int f = 0;
        if(p[f].size() < 2) f = 1;
        int x = use_machine({p[f][0], idx, p[f][1], idx + 1});
        p[(x % 2) ^ f].push_back(idx + 1);
        p[(x > 1) ^ f].push_back(idx);
        idx += 2;
    }
    if(idx == n - 1){
        int x = use_machine({0, idx});
        p[x].push_back(idx);
        return p[0].size();
    }
    int ret = p[0].size();
    while(idx < n){
        int f = 0;
        if(p[1].size() > p[0].size()) f = 1;
        vector <int> cur;
        for(auto &i : p[f]){
            if(idx == n) break;
            cur.push_back(i);
            cur.push_back(idx++);
        }
        int x = use_machine(cur);
        p[f ^ (x % 2)].push_back(cur.back());
        int diff = (x + 1) / 2;
        if(f == 1) ret += diff;
        else ret += cur.size() / 2 - diff;
    }
    return ret;
}

• Subtask 1: 92.2449 / 100