Submission #346215

#	Time	Username	Problem	Language	Result	Execution time	Memory
346215		poom2904	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	10 ms	512 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int cnt_A = 1,cnt_B = 0;
vector<int> A = {0},B;
int i=1;
const int cri=100;//if cnt_A or cnt_B >cri, do func2
void func1()
{
    while(max(cnt_A,cnt_B)<2)
    {
        vector<int> vec = {0,i};
        if(use_machine(vec))
        {
            cnt_B++;
            B.push_back(i);
        }
        else
        {
            cnt_A++;
            A.push_back(i);
        }
        i++;
    }
    while((min(cnt_A,cnt_B)<2 || max(cnt_A,cnt_B)<3) && max(cnt_A,cnt_B)<cri)
    {
        bool is_swapped = false;
        if(cnt_A<cnt_B)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
            is_swapped = true;
        }
        vector<int> vec = {i,A[0],i+1,A[1]};
        int res = use_machine(vec);
        if(res==0)
        {
            cnt_A+=2;
            A.push_back(i);
            A.push_back(i+1);
        }
        else if(res==1)
        {
            cnt_A++;
            cnt_B++;
            A.push_back(i+1);
            B.push_back(i);
        }
        else if(res==2)
        {
            cnt_A++;
            cnt_B++;
            A.push_back(i);
            B.push_back(i+1);
        }
        else
        {
            cnt_B+=2;
            B.push_back(i);
            B.push_back(i+1);
        }
        if(is_swapped)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
        }
        i+=2;
    }
    while(max(cnt_A,cnt_B)<cri)
    {
        bool is_swapped = false;
        if(cnt_A<cnt_B)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
            is_swapped = true;
        }
        vector<int> vec = {i,A[0],i+1,A[1],i+2,A[2]};
        int res = use_machine(vec);
        if(res&1)
        {
            cnt_B++;
            B.push_back(i);
        }
        else
        {
            cnt_A++;
            A.push_back(i);
        }
        if(res-(res&1)==0)
        {
            A.push_back(i+1);
            A.push_back(i+2);
            cnt_A+=2;
            i+=3;
        }
        else if(res-(res&1)==4)
        {
            B.push_back(i+1);
            B.push_back(i+2);
            cnt_B+=2;
            i+=3;
        }
        else
        {
            i++;
            vec = {B[0],i,B[1],A[0],i+1,A[1],i+2,A[2],i+3};
            res = use_machine(vec);
            if(res>4)
            {
                cnt_A++;
                cnt_B++;
                A.push_back(i);
                B.push_back(i+1);
            }
            else
            {
                cnt_A++;
                cnt_B++;
                A.push_back(i+1);
                B.push_back(i);
            }
            if(res%4==1)
            {
                cnt_A+=2;
                A.push_back(i+2);
                A.push_back(i+3);
            }
            else if(res%4==2)
            {
                cnt_A++;
                cnt_B++;
                A.push_back(i+2);
                B.push_back(i+3);
            }
            else if(res%4==3)
            {
                cnt_A++;
                cnt_B++;
                B.push_back(i+2);
                A.push_back(i+3);
            }
            else
            {
                cnt_B+=2;
                B.push_back(i+2);
                B.push_back(i+3);
            }
            i+=4;
        }
        if(is_swapped)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
        }
    }
}
void func2(int n)
{
    while(i<n)
    {
        bool is_swapped = false;
        if(A.size()<B.size())
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
            is_swapped = true;
        }
        int minn = min(int(A.size()),n-i);
        vector<int> vec(minn*2);
        for(int j=0;j<minn;j++)
        {
            vec[j*2] = i+j;
            vec[j*2+1] = A[j];
        }
        int res = use_machine(vec);
        if(res&1)
        {
            cnt_B++;
            B.push_back(i);
        }
        else
        {
            cnt_A++;
            A.push_back(i);
        }
        cnt_A += minn-1-res/2;
        cnt_B += res/2;
        if(is_swapped)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
        }
        i+=minn;
    }
}
int count_mushrooms(int n) {
    if(n<=227)
    {
        while(i<n)
        {
            vector<int> vec = {0,i};
            if(use_machine(vec))cnt_B++;
            else cnt_A++;
            i++;
        }
        return cnt_A;
    }
	func1();
    func2(n);
	return cnt_A;
}

• Subtask 1: 100 / 100