Submission #1235309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235309		stanirina	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 ms	432 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;

int count_mushrooms(int n) {
    if(n<452){
        int ans=1;
        for (int i = 1; i +1< n; i+=2){
            ans+=(2-use_machine({i,0,i+1}));
        }
        if(n%2==0)ans+=(1-use_machine({0,n-1}));
        return ans;
    }
	int ans=1;
	vector<int> a;
	vector<int> b;
	a.clear();
	b.clear();
	a.push_back(0);
	
	if(use_machine({0,1})==1)b.push_back(1);
	else a.push_back(1);
	if(use_machine({0,2})==1)b.push_back(2);
	else a.push_back(2);
	if(use_machine({0,3})==1)b.push_back(3);
	else a.push_back(3);
	
	
	for (int i = 4; i < 280; i+=2){
        if(a.size()>=2){
            int c=use_machine({i,a[0],i+1,a[1]});
            if(c==0){
                a.push_back(i);
                a.push_back(i+1);
            }
            else if(c==1){
                b.push_back(i);
                a.push_back(i+1);
            }
            else if(c==2){
                a.push_back(i);
                b.push_back(i+1);
            }
            else if(c==3){
                b.push_back(i);
                b.push_back(i+1);
            }
        }
        
        else{
            int c=use_machine({i,b[0],i+1,b[1]});
            if(c==0){
                b.push_back(i);
                b.push_back(i+1);
            }
            else if(c==1){
                a.push_back(i);
                b.push_back(i+1);
            }
            else if(c==2){
                b.push_back(i);
                a.push_back(i+1);
            }
            else if(c==3){
                a.push_back(i);
                a.push_back(i+1);
            }
        }
	}
	ans=a.size();
    vector<int> m;
    int sz=280;
    for(int i=280;i<n;i+=280){
        m.clear();
        int j=i;
        for(j;j<min(n,i+(int)a.size());j++){
            m.push_back(j);    
            m.push_back(a[j-i]);
        }
        if(m.size()>0)ans+=(a.size()-(use_machine(m)+1)/2);
        m.clear();
        for(j;j<min(n,i+280);j++){
            m.push_back(b[j-i-a.size()]);
            m.push_back(j);
        }
        if(m.size()>0)ans+=(use_machine(m)+1)/2;
    }

	return ans;
}

• Subtask 1: 0 / 100