Submission #1223556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223556		Ludissey	Counting Mushrooms (IOI20_mushrooms)	C++20	25 / 100	27 ms	832 KiB

mushrooms

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

using namespace std;

#define sz(a) (int)a.size()
#define all(a) (a.begin(), a.end())

int N;
int sm=0;

vector<int> a;
vector<int> b;
const int MXSTOP=50000;

void A();
void B();

void fase2(int st){
    if(sz(a)>=sz(b)){
        int j=1;
        for (int i = st; i < N; i++)
        {
            a[j]=i;
            j+=2;
            if(j>=sz(a)) {
                sm+=(sz(a)-use_machine(a))/2;
                j=1;
            }
        }
        if(j>1) {
            a.resize(j);
            sm+=(sz(a)-use_machine(a))/2;
        }
    }else{
        int j=1;
        for (int i = st; i < N; i++)
        {
            b[j]=i;
            j+=2;
            if(j>=sz(b)) {
                sm+=use_machine(b)/2;
                j=1;
            }
        }
        if(j>1) {
            b.resize(j);
            sm+=use_machine(b)/2;
        }
    }

}


void A(int st){
    sm+=2;
    for (int j = st; j+1 < N; j+=2)
    {
        if(max(sz(a),sz(b))>MXSTOP*2) {
            fase2(j);
            return;
        }
        int um=use_machine({0,j,st-1,j+1});
        if(um==0) {
            a.push_back(-1);
            a.push_back(j);
            a.push_back(-1);
            a.push_back(j+1);
        }else if(um==1) {
            a.push_back(-1);
            a.push_back(j);
            if(sz(b)>0) b.push_back(-1);
            b.push_back(j+1);
        }else if(um==2){
            if(sz(b)>0) b.push_back(-1);
            b.push_back(j);
            a.push_back(-1);
            a.push_back(j+1);
        }else{
            if(sz(b)>0) b.push_back(-1);
            b.push_back(j);
            b.push_back(-1);
            b.push_back(j+1);
        }
        sm+=2-(um+1)/2;
    }
    if(st%2==(N-1)%2) sm+=1-use_machine({0,(int)N-1});
}

void B(int st){
    sm+=1;
    for (int j = st; j+1 < N; j+=2)
    {
        if(max(sz(a),sz(b))>MXSTOP*2) {
            fase2(j);
            return;
        }
        int um=use_machine({1,j,st-1,j+1});
        if(um==0) {
            b.push_back(-1);
            b.push_back(j);
            b.push_back(-1);
            b.push_back(j+1);
        }else if(um==1) {
            a.push_back(-1);
            a.push_back(j);
            b.push_back(-1);
            b.push_back(j+1);
        }else if(um==2){
            b.push_back(-1);
            b.push_back(j);
            a.push_back(-1);
            a.push_back(j+1);
        }else{
            a.push_back(-1);
            a.push_back(j);
            a.push_back(-1);
            a.push_back(j+1);
        }
        sm+=(um+1)/2;
    }
    if(st%2==(N-1)%2) sm+=1-use_machine({0,(int)N-1});
}

int count_mushrooms(int n) {
    N=n;
    sm=0;
    a.clear();
    b.clear();
    a.push_back(0);
    if(use_machine({0,1})==0) {
        a.push_back(-1);
        a.push_back(1);
        A(2);
    }
    else{
        b.push_back(1);
        if(n==2) sm=1;
        else{
            if(use_machine({0,2})==0) {
                a.push_back(-1);
                a.push_back(2);
                A(3);
            }
            else{
                b.push_back(-1);
                b.push_back(2);
                B(3);
            }
        }
    }

    return sm;
}

• Subtask 1: 25 / 100