Submission #1205187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205187		notme	Counting Mushrooms (IOI20_mushrooms)	C++20	53.81 / 100	3 ms	432 KiB

mushrooms

#include <bits/stdc++.h>
#define pb push_back
#include "mushrooms.h"
using namespace std;
vector < int > a, b;
int base;
int count_mushrooms(int n)
{
    base = 140;
    a.pb(0);
    int i = 1;
    while(i < n && a.size() < base && b.size() < base)
    {
        vector < int > curr;
        curr.pb(0);
        curr.pb(i);
        int fb = use_machine(curr);
        if(fb)b.pb(i);
        else a.pb(i);
        i ++;
    }
  /*  for (auto x: a)
        cout << x << " ";
    cout << endl;
    for (auto x: b)
        cout << x << " " ;
    cout << endl;*/
    int cnta = a.size(), cntb = b.size();
    if(a.size() == base)
    {
        while(i < n)
        {
            vector < int > addon;
            for (int j = i; j < min(n, i + base - 1); ++ j)
                addon.pb(j);
            vector < int > curr;
            int posa = 0;
            for (auto x: addon)
            {
                curr.pb(a[posa]);
                curr.pb(x);
                posa ++;
            }
            curr.pb(a[posa]);
            int val = use_machine(curr);
            cntb += val/2;
            cnta += addon.size() - val/2;
            i += addon.size();
        }
    }
    else
    {
        while(i < n)
        {
            vector < int > addon;
            for (int j = i; j < min(n, i + base - 1); ++ j)
                addon.pb(j);
            vector < int > curr;
            int posb = 0;
            for (auto x: addon)
            {
                curr.pb(b[posb]);
                curr.pb(x);
                posb ++;
            }
            curr.pb(b[posb]);
            int val = use_machine(curr);
            cnta += val/2;
            cntb += addon.size() - val/2;
            i += addon.size();
        }
    }

	return cnta;
}

• Subtask 1: 53.8095 / 100