Submission #1219132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219132		JooDdae	Counting Mushrooms (IOI20_mushrooms)	C++20	91.87 / 100	3 ms	444 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);
    v[use_machine({0, 1})].push_back(1);
    if(n == 2) return v[0].size();
    v[use_machine({0, 2})].push_back(2);
    if(n == 3) return v[0].size();

    int u = 3, k = v[0].size() > v[1].size() ? 0 : 1;
    for(int i=0;i<100 && u+1<n;i++, u += 2) {
        int re = use_machine({v[k][0], u, v[k][1], u+1});
        v[k ^ (re >> 1)].push_back(u);
        v[k ^ (re & 1)].push_back(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: 91.8699 / 100