제출 #1226225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226225		PVM_pvm	버섯 세기 (IOI20_mushrooms)	C++20	70.19 / 100	3 ms	472 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define desr 80
int count_mushrooms(int n) {
	vector<int> ata;
	vector<int> bta;
	ata.push_back(0);
	int klk=1;
	int cur=1;
    while (true)
    {
        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++;
        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: 70.1863 / 100