Submission #1231297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231297		VMaksimoski008	Counting Mushrooms (IOI20_mushrooms)	C++20	56.64 / 100	3 ms	428 KiB

mushrooms

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

int count_mushrooms(int n) {
	int ans = 1;
    
    if(n < 226) {
        for(int i=1; i<n; i++)
            ans += 1 - use_machine({ 0, i });
        return ans;
    }

    vector<int> t[2];
    t[0].push_back(0);
    
    const int SZ = 95;

    int lst = 0;
    for(int i=1; i<n; i++) {
        if(t[0].size() == SZ || t[1].size() == SZ) {
            lst = i;
            break;
        }
        
        int v = use_machine({ 0, i });
        ans += 1 - v;
        t[v].push_back(i);
    }

    int p = 0;
    if(t[1].size() == SZ) p = 1;

    for(int i=lst; i<n; i+=SZ-1) {
        vector<int> A;
        for(int j=i; j<min(n, i+SZ-1); j++)
            A.push_back(j);
        
        vector<int> to_get;
        for(int j=0; j<A.size(); j++) {
            to_get.push_back(t[p][j]);
            to_get.push_back(A[j]);
        }
        to_get.push_back(t[p][A.size()]);

        int v = use_machine(to_get);

        if(!p) {
            ans += (2 * A.size() - v) / 2;
        } else {
            ans += v / 2;
        }
    }

    return ans;
}

• Subtask 1: 56.6416 / 100