Submission #364949

#	Time	Username	Problem	Language	Result	Execution time	Memory
364949		leinad2	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	11 ms	548 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
    if(n<=200)
    {
        int ans=1;
        for(int i=1;i<n;i++)
        {
            vector<int>v;
            v.push_back(0);v.push_back(i);
            if(use_machine(v)==0)ans++;
        }
        return ans;
    }
    vector<int>v[2];
    v[0].push_back(0);
    vector<int>qr;
    qr.push_back(0);qr.push_back(1);
    v[use_machine(qr)].push_back(1);
    qr.pop_back();qr.push_back(2);
    v[use_machine(qr)].push_back(2);
    int y=0;
    if(v[0].size()<2)y=1;
    qr.clear();
    qr.push_back(v[y][0]);
    qr.push_back(3);
    qr.push_back(v[y][1]);
    qr.push_back(4);
    int ans=use_machine(qr);
    v[(ans/2+y)%2].push_back(3);
    v[(ans+y)%2].push_back(4);
    int x=0;
    if(v[0].size()<3)x=1;
    int bu=45;
    for(int i=1;i<bu;i++)
    {
        vector<int>q;
        q.push_back(v[x][0]);q.push_back(5*i);q.push_back(v[x][1]);q.push_back(5*i+1);q.push_back(v[x][2]);q.push_back(5*i+2);
        int ans=use_machine(q);
        if(ans/2==1)
        {
            v[(ans+x)%2].push_back(5*i+2);
            if(v[1-x].size()<2)
            {
                vector<int>qr;
                qr.push_back(v[x][0]);
                qr.push_back(5*i+3);
                qr.push_back(v[x][1]);
                qr.push_back(5*i+4);
                int ans=use_machine(qr);
                v[(ans/2+x)%2].push_back(5*i+3);
                v[(ans+x)%2].push_back(5*i+4);
                qr.clear();
                qr.push_back(v[x][0]);
                qr.push_back(5*i);
                ans=use_machine(qr);
                v[(ans+x)%2].push_back(5*i);
                v[(ans+x+1)%2].push_back(5*i+1);
            }
            else
            {
                vector<int>qr;
                qr.push_back(v[1-x][0]);
                qr.push_back(5*i);
                qr.push_back(v[1-x][1]);
                qr.push_back(v[x][0]);
                qr.push_back(5*i+1);
                qr.push_back(v[x][1]);
                qr.push_back(5*i+3);
                qr.push_back(v[x][2]);
                qr.push_back(5*i+4);
                int ans=use_machine(qr);
                ans--;
                v[(ans/4+x+1)%2].push_back(5*i);
                v[(ans/4+x)%2].push_back(5*i+1);
                ans%=4;
                v[(ans/2+x)%2].push_back(5*i+3);
                v[(ans+x)%2].push_back(5*i+4);
            }
        }
        else
        {
            v[(ans/4+x)%2].push_back(5*i);
            v[(ans/4+x)%2].push_back(5*i+1);
            v[(ans+x)%2].push_back(5*i+2);
            vector<int>qr;
            qr.push_back(v[x][0]);
            qr.push_back(5*i+3);
            qr.push_back(v[x][1]);
            qr.push_back(5*i+4);
            int ans=use_machine(qr);
            v[(ans/2+x)%2].push_back(5*i+3);
            v[(ans+x)%2].push_back(5*i+4);
        }
    }
    int jump;
    int ret=v[0].size();
    for(int i=5*bu;i<n;i+=jump)
    {
        int k;
        if(v[0].size()>v[1].size())
        {
            k=0;
            jump=v[0].size();
        }
        else
        {
            k=1;
            jump=v[1].size();
        }
        vector<int>quer;
        for(int j=i;j<min(i+jump, n);j++)
        {
            quer.push_back(v[k][j-i]);
            quer.push_back(j);
        }
        int ans=use_machine(quer);
        if(k)ret+=(ans/2+ans%2);
        else ret-=(ans/2+ans%2),ret+=(min(i+jump, n)-i);
        v[(ans%2)^k].push_back(min(i+jump, n)-1);
    }
    return ret;
}

• Subtask 1: 100 / 100