제출 #1226229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226229		PVM_pvm	Counting Mushrooms (IOI20_mushrooms)	C++20	91.87 / 100	3 ms	456 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define desr 100
int count_mushrooms(int n) {
	vector<int> ata;
	vector<int> bta;
	ata.push_back(0);
	int klk=1;
	int cur=1;
    while (true)
    {
        if (cur==n-1 || (ata.size()<2 && bta.size()<2) )
        {
            vector<int> qu(2);
            qu[0]=0;
            qu[1]=cur;
            int ans=use_machine(qu);
            if (ans==0)
            {
                ata.push_back(cur);
                klk++;
            }
            else
            {
                bta.push_back(cur);
            }
            cur++;
        }
        else if (ata.size()>=2)
        {
            vector<int> qu(4);
            qu[0]=cur;
            qu[1]=ata[0];
            qu[2]=cur+1;
            qu[3]=ata[1];
            int ans=use_machine(qu);
            if (ans%2==0)
            {
                ata.push_back(cur);
                klk++;
            }
            else
            {
                bta.push_back(cur);
                ans--;
            }
            if (ans==0)
            {
                ata.push_back(cur+1);
                klk++;
            }
            else
            {
                bta.push_back(cur+1);
            }
            cur+=2;
        }
        else
        {
            vector<int> qu(4);
            qu[0]=cur;
            qu[1]=bta[0];
            qu[2]=cur+1;
            qu[3]=bta[1];
            int ans=use_machine(qu);
            if (ans%2==1)
            {
                ans--;
                ata.push_back(cur);
                klk++;
            }
            else
            {
                bta.push_back(cur);
            }
            if (ans==2)
            {
                ata.push_back(cur+1);
                klk++;
            }
            else
            {
                bta.push_back(cur+1);
            }
            cur+=2;
        }
        if (ata.size()+bta.size()==n) return klk;
        if (ata.size()>=desr) break;
        if (bta.size()>=desr) break;
    }
    //cout<<klk<<" "<<cur<<"\n";
    while (cur<n)
    {
        int sz=n-cur;
        if (sz<ata.size())
        {
            ///prosto dovyrshi
            vector<int> qu(2*sz+1);
            for (int q=0;q<sz;q++)
            {
                qu[2*q]=ata[q];
                qu[2*q+1]=cur+q;
            }
            qu[2*sz]=ata[sz];
            int ans=use_machine(qu);
            klk+=(sz-ans/2);
            cur=n;
        }
        else if (sz<bta.size())
        {
            ///prosto dovyrshi
            vector<int> qu(2*sz+1);
            for (int q=0;q<sz;q++)
            {
                qu[2*q]=bta[q];
                qu[2*q+1]=cur+q;
            }
            qu[2*sz]=bta[sz];
            int ans=use_machine(qu);
            klk+=(ans/2);
            cur=n;
        }
        else if (ata.size()>bta.size())
        {
            //cerr<<"a e "<<ata.size()<<"\n";
            sz=ata.size();
            vector<int> qu(2*sz);
            for (int q=0;q<sz;q++)
            {
                qu[2*q]=cur+q;
                qu[2*q+1]=ata[q];
            }
            int ans=use_machine(qu);
            if (ans%2==0)
            {
                ///cur e A
                ata.push_back(cur);
            }
            else
            {
                bta.push_back(cur);
                ans++;
            }
            klk+=(sz-ans/2);
            cur+=sz;
            //cout<<klk<<"\n";
        }
        else
        {
            //cerr<<"b e "<<bta.size()<<"\n";
            sz=bta.size();
            vector<int> qu(2*sz);
            for (int q=0;q<sz;q++)
            {
                qu[2*q]=cur+q;
                qu[2*q+1]=bta[q];
            }
            int ans=use_machine(qu);
            if (ans%2==1)
            {
                ///cur e A
                ans++;
                ata.push_back(cur);
            }
            else bta.push_back(cur);
            klk+=(ans/2);
            cur+=sz;
        }
    }
    return klk;
}

• Subtask 1: 91.8699 / 100