Submission #1205564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205564		notme	Counting Mushrooms (IOI20_mushrooms)	C++20	92.24 / 100	3 ms	452 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 = 90;
    a.pb(0);

    vector < int > curr;
    curr.pb(0);
    curr.pb(1);
    int fb = use_machine(curr);
    if(fb)b.pb(1);
    else a.pb(1);

    if(n > 2)
    {
        curr.clear();
        curr.pb(0);
        curr.pb(2);
        int fb = use_machine(curr);
        if(fb)b.pb(2);
        else a.pb(2);
    }
    else return a.size();

    int i = 3;
    while(i+1 < n && a.size() < base && b.size() < base)
    {
        if(a.size() >= 2)
        {
            vector < int > curr;
            curr.pb(i);
            curr.pb(a[0]);
            curr.pb(i+1);
            curr.pb(a[1]);

            int fb = use_machine(curr);

            if(fb % 2 == 1)b.pb(i);
            else a.pb(i);

            if(fb >= 2)b.pb(i+1);
            else a.pb(i+1);
            i += 2;
        }
        else
        {
            vector < int > curr;
            curr.pb(i);
            curr.pb(b[0]);
            curr.pb(i+1);
            curr.pb(b[1]);

            int fb = use_machine(curr);

            if(fb % 2 == 1)a.pb(i);
            else b.pb(i);

            if(fb >= 2)a.pb(i+1);
            else b.pb(i+1);
            i += 2;
        }

    }
    /*  for (auto x: a)
          cout << x << " ";
      cout << endl;
      for (auto x: b)
          cout << x << " " ;
      cout << endl;*/
    int cnta = a.size(), cntb = b.size();

    while(i < n)
    {
        if(a.size() > b.size())
        {
            vector < int > addon;

            for (int j = i; j < min(n, i + (int)a.size() - 1); ++ j)
                addon.pb(j);
            vector < int > curr;
            int posa = 0;
            for (auto x: addon)
            {
                curr.pb(x);
                curr.pb(a[posa]);

                posa ++;
            }
            //   curr.pb(a[posa]);
            int val = use_machine(curr);
            cntb += (val/2 + val%2);
            cnta += addon.size() - (val/2 + val%2);
            if(val % 2 == 0)a.pb(i);
            else b.pb(i);
            i += addon.size();
        }
        else
        {
            vector < int > addon;
            for (int j = i; j < min(n, i + (int)b.size() - 1); ++ j)
                addon.pb(j);
            vector < int > curr;
            int posb = 0;
            for (auto x: addon)
            {
                curr.pb(x);
                curr.pb(b[posb]);
                posb ++;
            }
            //curr.pb(b[posb]);
            int val = use_machine(curr);
            cnta += val/2 + val%2;
            cntb += addon.size() - val/2 - (val%2);
            if(val % 2 == 0)b.pb(i);
            else a.pb(i);
            i += addon.size();
        }
    }

    assert(cnta + cntb == n);
    return cnta;
}

• Subtask 1: 92.2449 / 100