Submission #364805

#	Time	Username	Problem	Language	Result	Execution time	Memory
364805		leinad2	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	12 ms	512 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
    if(n<=4)
    {
        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>qr;
	int a=0, b=0, x=0, i, j;
	qr.push_back(0);
	qr.push_back(1);
	int ans1=use_machine(qr);
	qr.pop_back();
	qr.push_back(2);
	int ans2=use_machine(qr);
	vector<int>v1, v2;
	if(ans1&&ans2)
    {
        v2.push_back(0);
        x=1;
        v1.push_back(1);v1.push_back(2);
        a=1;
        b=2;
    }
    else if(ans1)
    {
        v1.push_back(0);v1.push_back(2);
        v2.push_back(1);
        a=0;
        b=2;
    }
    else if(ans2)
    {
        v1.push_back(0);v1.push_back(1);
        v2.push_back(2);
        a=0;
        b=1;
    }
    else
    {
        v1.push_back(0);v1.push_back(1);v1.push_back(2);
        a=0;
        b=1;
    }
    int bu=(int)sqrt(n);
    for(i=1;i++<bu;)
    {
        vector<int>v;
        v.push_back(a);
        v.push_back(2*i-1);
        v.push_back(b);
        v.push_back(2*i);
        int ans=use_machine(v);
        if(ans>=2)v2.push_back(2*i-1);
        else v1.push_back(2*i-1);
        if(ans%2==1)v2.push_back(2*i);
        else v1.push_back(2*i);
    }
    if(v1.size()<v2.size())
    {
        v1.clear();
        while(v2.size())v1.push_back(v2.back()),v2.pop_back();
        x=1-x;
    }
    int ans=v1.size();
    for(i=2*bu+1;i<n;i+=v1.size())
    {
        vector<int>v;
        for(j=i;j<min(i+(int)v1.size(), n);j++)
        {
            v.push_back(v1[j-i]);
            v.push_back(j);
        }
        int q=use_machine(v);
        ans+=v.size()/2;
        ans-=(q/2+q%2);
    }
    if(x==1)return n-ans;
    else return ans;
}

• Subtask 1: 80.427 / 100