Submission #1133204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133204		StefanSebez	Counting Mushrooms (IOI20_mushrooms)	C++20	92.24 / 100	1890 ms	783224 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
mt19937 rng(time(0));
int K=82;
short dp[20001][20001];
int count_mushrooms(int n){
    int res=0;
    vector<int>ind[2];ind[0].pb(0);
    /*int i=1;
    for(;i<min(3,n);i++){
        vector<int>temp={0,i};
        if(use_machine(temp)==0) ind[0].pb(i);
        else ind[1].pb(i);
    }
    while(i+1<n&&max(ind[0].size(),ind[1].size())<K){
        if(ind[0].size()>=2){
            vector<int>temp={i,ind[0][0],i+1,ind[0][1]};
            int x=use_machine(temp);
            if(x==3) ind[1].pb(i),ind[1].pb(i+1);
            if(x==2) ind[0].pb(i),ind[1].pb(i+1);
            if(x==1) ind[1].pb(i),ind[0].pb(i+1);
            if(x==0) ind[0].pb(i),ind[0].pb(i+1);
        }
        else{
            vector<int>temp={i,ind[1][0],i+1,ind[1][1]};
            int x=use_machine(temp);
            if(x==3) ind[0].pb(i),ind[0].pb(i+1);
            if(x==2) ind[1].pb(i),ind[0].pb(i+1);
            if(x==1) ind[0].pb(i),ind[1].pb(i+1);
            if(x==0) ind[1].pb(i),ind[1].pb(i+1);
        }
        i+=2;
    }*/
    for(int i=1;i<n;i++){
        for(int k=1;k<=n;k++){
            if(i-(k+1>>1)<=0||i-2<=0){dp[i][k]=1;continue;}
            dp[i][k]=min(dp[i-2][k+2],dp[i-(k+1>>1)][k+1])+1;
        }
    }
    for(int i=1;i<n;){
        int k=ind[0].size()+ind[1].size(),I=n-i;
        if(I>=2&&dp[I][k]==dp[I-2][k+2]+1&&max(ind[0].size(),ind[1].size())>=2){
            if(ind[0].size()>=2){
                vector<int>temp={i,ind[0][0],i+1,ind[0][1]};
                int x=use_machine(temp);
                if(x==3) ind[1].pb(i),ind[1].pb(i+1);
                if(x==2) ind[0].pb(i),ind[1].pb(i+1);
                if(x==1) ind[1].pb(i),ind[0].pb(i+1);
                if(x==0) ind[0].pb(i),ind[0].pb(i+1);
            }
            else{
                vector<int>temp={i,ind[1][0],i+1,ind[1][1]};
                int x=use_machine(temp);
                if(x==3) ind[0].pb(i),ind[0].pb(i+1);
                if(x==2) ind[1].pb(i),ind[0].pb(i+1);
                if(x==1) ind[0].pb(i),ind[1].pb(i+1);
                if(x==0) ind[1].pb(i),ind[1].pb(i+1);
            }
            i+=2;
        }
        else{
            vector<int>temp;
            if(ind[0].size()>=ind[1].size()){
                int k=ind[0].size(),j=i;
                for(int ct=0;i<n&&ct<k;i++,ct++){
                    temp.pb(i);
                    temp.pb(ind[0][ct]);
                }
                int x=use_machine(temp),sz=temp.size();
                if(x%2==0) ind[0].pb(j),res--;
                else ind[1].pb(j);
                res+=sz-x>>1;
            }
            else{
                int k=ind[1].size(),j=i;
                for(int ct=0;i<n&&ct<k;i++,ct++){
                    temp.pb(i);
                    temp.pb(ind[1][ct]);
                }
                int x=use_machine(temp),sz=temp.size();
                if(x%2==1) ind[0].pb(j),res--;
                else ind[1].pb(j);
                res+=x+1>>1;
            }
        }
    }
    res+=ind[0].size();
    return res;
}

• Subtask 1: 92.2449 / 100