제출 #1133196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133196		StefanSebez	버섯 세기 (IOI20_mushrooms)	C++20	74.59 / 100	3 ms	468 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,p=322;
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;){
        int r=rng()%1000;
        if(r<=p&&i+1<n&&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: 74.5875 / 100