제출 #1194680

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

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int x=100,y=120;
vector<int> a,b,v;
int count_mushrooms(int n) {
    int c;
    if(n==2)
    {
        c=use_machine({0,1});
        if(c==1)return 1;
        return 2;
    }

    int ans=1;
    a.push_back(0);
    c=use_machine({0,1,2});
    if(c==2)
    {
        a.push_back(2);
        b.push_back(1);
        ans++;
    }
    if(c==0)
    {
        a.push_back(1);
        a.push_back(2);
        ans+=2;
    }
    if(c==1)
    {
        c=use_machine({0,1});
        if(c==1)b.pb(1);
        else ans++,a.pb(1);
        b.push_back(2);
    }

    for(int i=3;i<min(n,y);i+=2)
    {
        if(i==n-1)
        {
            c=use_machine({0,i});
            if(c==0)ans++,a.pb(i);
            else b.pb(i);
            break;
        }
        if(a.size()>=2)
        {
            c=use_machine({a[0],i,a[1],i+1});
            if(c>=2)b.pb(i);
            else ans++,a.pb(i);

            if(c%2==1)b.pb(i+1);
            else ans++,a.pb(i+1);
        }
        else
        {
            c=use_machine({b[0],i,b[1],i+1});
            if(c<2)b.pb(i);
            else ans++,a.pb(i);

            if(c%2==0)b.pb(i+1);
            else ans++,a.pb(i+1);
        }
    }

    int i=y+1;
    while(i<n)
    {
        vector<int> h;
        if(a.size()>b.size())
        {
            for(int j=0;j<a.size();j++)
            {
                h.push_back(a[j]);
                if(i==n)break;
                h.push_back(i++);
            }
            c=use_machine(h);
            ans+=(h.size()-1)/2-c/2;
            if(h.size()%2==0)
            {
                if(c%2==0)ans++,a.pb(h[h.size()-1]);
                else b.pb(h[h.size()-1]);
            }
        }
        else
        {
            for(int j=0;j<b.size();j++)
            {
                h.push_back(b[j]);
                if(i==n)break;
                h.push_back(i++);
            }
            c=use_machine(h);
            ans+=c/2;
            if(h.size()%2==0)
            {
                if(c%2==0)b.pb(h[h.size()-1]);
                else ans++,a.pb(h[h.size()-1]);
            }
        }

        /*for(int j=0;j<h.size();j++)
            cout<<h[j]<<" ";
        cout<<endl;*/
    }

    return ans;
}

• Subtask 1: 91.8699 / 100