Submission #1219123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219123		JooDdae	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	464 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int use_machine(std::vector<int> x);

int count_mushrooms(int n) {
    int c[2] = {0, 0};
    vector<int> v[2]; v[0].push_back(0);
    int u = 1;
    while(u < n) {
        int k = v[0].size() > v[1].size() ? 0 : 1;
        
        vector<int> q;
        for(int i=0;i<v[k].size() && u<n;i++) {
            q.push_back(v[k][i]);
            q.push_back(u++);
        }

        int re = use_machine(q);
        v[k ^ (re % 2)].push_back(q.back());

        int S = q.size()/2-1; re /= 2;
        c[k] += S-re, c[!k] += re;
    }
    return v[0].size() + c[0];
}

• Subtask 1: 80.7143 / 100