Submission #1293403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293403		lambd47	Counting Mushrooms (IOI20_mushrooms)	C++20	99.56 / 100	5 ms	512 KiB

mushrooms

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

#define ll long long
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)


int count_mushrooms(int n) {
    vector<int> ids(n-1);
    iota(all(ids),1);
    reverse(all(ids));
    vector<int> tipo[2];
    tipo[0].clear();tipo[1].clear();
    tipo[0].push_back(0);
    vector<int> aux;
    int resp=0;
    vector<int> fila;
    if(sz(ids)<100){
        while(!ids.empty() && sz(tipo[0])<3 && sz(tipo[1])<3){
            aux.clear();
            aux.push_back(0);
            aux.push_back(ids.back());
            int v=use_machine(aux);
            tipo[v].push_back(ids.back());
            ids.pop_back();
        }
    }
    else{
        while(!ids.empty() && sz(tipo[0])<2 && sz(tipo[1])<2){
            aux.clear();
            aux.push_back(0);
            aux.push_back(ids.back());
            int v=use_machine(aux);
            tipo[v].push_back(ids.back());
            ids.pop_back();
        }
        int at=0;if(sz(tipo[1])==2)at=1;
        while(!ids.empty() && sz(tipo[0])<3 && sz(tipo[1])<3){
            aux.clear();
            int a=ids.back();ids.pop_back();
            int b=ids.back();ids.pop_back();
            aux={tipo[at][0],a,tipo[at][1],b};
            int v=use_machine(aux);
            if(v&1)tipo[at^1].push_back(b);
            else tipo[at].push_back(b);
            if(v&2)tipo[at^1].push_back(a);
            else tipo[at].push_back(a);
        }
    }



    auto goat=[&](int at,int a, int b, int c, int d)->void{
        aux.clear();aux={tipo[at^1][0],a,tipo[at^1][1],tipo[at][0],b,tipo[at][1],c,tipo[at][2],d};
        int v=use_machine(aux);
        v--;
        if(v&1){
            tipo[at^1].push_back(d);
        }else{
            tipo[at].push_back(d);
        }
        if(v&2){
            tipo[at^1].push_back(c);
        }
        else tipo[at].push_back(c);
        if(v&4){
            tipo[at].push_back(a);
            tipo[at^1].push_back(b);
        }
        else{
            tipo[at].push_back(b);
            tipo[at^1].push_back(a);
        }
    };

    auto op=[&](int a,int b, int c, int at)->void{
        aux.clear();
        aux={tipo[at][0],a,tipo[at][1],b,tipo[at][2],c};
        int v=use_machine(aux);
        if(v&1){
            tipo[at^1].push_back(c);
            v--;
        }
        else tipo[at].push_back(c);
        if(v==4){
            tipo[at^1].push_back(a);
            tipo[at^1].push_back(b);
        }
        else if(v==2){
            if(sz(tipo[at^1])<2){
                aux.clear();aux={0,a};v=use_machine(aux);
                tipo[v].push_back(a);
                tipo[v^1].push_back(b);
            }else{
                int d=ids.back();ids.pop_back();
                int e=ids.back();ids.pop_back();
                goat(at,a,b,d,e);
            }
        }
        else{
            tipo[at].push_back(a);
            tipo[at].push_back(b);
        }
    };
    int at=0;
    if(sz(tipo[1])>=3)at=1;
    int m=95;
    while(sz(ids)>6 && sz(tipo[0])<m && sz(tipo[1])<m){
        int a=ids.back();ids.pop_back();
        int b=ids.back();ids.pop_back();
        int c=ids.back();ids.pop_back();
        op(a,b,c,at);
    }
    if(sz(ids)<=6){
        while(sz(ids)>0){
            int x=ids.back();
            aux.clear();
            aux={0,x};
            int v=use_machine(aux);
            tipo[v].push_back(x);
            ids.pop_back();
        }
    }
    if(sz(ids)==0){
        return resp+sz(tipo[0]);
    }


    at=0;
    if(sz(tipo[1])>=sz(tipo[0]))at=1;

    while(!ids.empty()){
        int vida=sz(tipo[at])-1;
        aux.clear();
        while(vida>=0 && !ids.empty()){
            aux.push_back(tipo[at][vida]);
            aux.push_back(ids.back());
            ids.pop_back();
            vida--;
        }
        int v=use_machine(aux);
        int oposto=0;
        if(v&1){
            v++;
            oposto=1;
        }
        if(at==1){
            resp+=v/2;
            if(oposto==1){
                resp--;
                tipo[0].push_back(aux.back());
            }
            else{
                tipo[1].push_back(aux.back());
            }
        }
        else{
            resp+=sz(aux)/2-v/2;
            if(oposto==1){
                tipo[1].push_back(aux.back());
            }
            else{
                tipo[0].push_back(aux.back());
                resp--;
            }
        }
        if(sz(tipo[at^1])>sz(tipo[at]))at^=1;
    }
    return resp+sz(tipo[0]);
}

• Subtask 1: 99.5595 / 100