Submission #364829

#	Time	Username	Problem	Language	Result	Execution time	Memory
364829		leinad2	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	11 ms	524 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 a, b, x=0;
    if(v[0].size()>=2)a=v[0][0],b=v[0][1];
    else a=v[1][0],b=v[1][1],x=1;
    int bu=80;
    for(int i=1;i++<bu;)
    {
        vector<int>q;
        q.push_back(a);q.push_back(2*i-1);q.push_back(b);q.push_back(2*i);
        int ans=use_machine(q);
        if(ans<2)v[x].push_back(2*i-1);
        else v[1-x].push_back(2*i-1);
        if(ans%2==0)v[x].push_back(2*i);
        else v[1-x].push_back(2*i);
    }
    int jump;
    int ret=v[0].size();
    for(int i=2*bu+1;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: 92.623 / 100