제출 #1132874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132874		StefanSebez	버섯 세기 (IOI20_mushrooms)	C++20	10 / 100	54 ms	424 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=3;
int count_mushrooms(int n){
    int res=1;
    int a[n+10]={0};
    for(int i=1;i<min(K,n);i++){
        vector<int>temp={0,i};
        if(use_machine(temp)==1) a[i]=1;
        else res++;
    }
    int num[2]={0};
    for(int i=0;i<min(K,n);i++){
        num[a[i]]++;
        //printf("%i ",a[i]);
    }
    //printf("\n");
    //printf("%i %i\n",num[0],num[1]);
    if(num[0]>=num[1]){
        vector<int>ind;
        for(int i=0;i<min(K,n);i++) if(a[i]==0) ind.pb(i);
        //for(auto i:ind) printf("%i ",i);printf("\n");
        int k=ind.size();
        //int poslednji=n;
        for(int i=K;i<n;i+=k-1){
            //printf("%i\n",i);
            //poslednji=i+k-1;
            vector<int>temp={ind[0]};
            for(int j=i,ct=1;j<min(i+k-1,n);j++){
                temp.pb(j);
                temp.pb(ind[ct++]);
            }
            //for(auto j:temp) printf("%i ",j);printf("\n");
            int x=use_machine(temp);
            int sz=temp.size();
            //printf("%i\n",K-x);
            res+=sz-1-x>>1;
        }
        //printf("%i %i\n",res,poslednji);
        /*for(int i=poslednji;i<n;i++){
            vector<int>temp={0,i};
            if(use_machine(temp)==1) a[i]=1;
            else res++;
        }*/
    }
    else{
        vector<int>ind;
        for(int i=0;i<min(K,n);i++) if(a[i]==1) ind.pb(i);
        //for(auto i:ind) printf("%i ",i);printf("\n");
        int k=ind.size();
        //int poslednji=n;
        for(int i=K;i<n;i+=k-1){
            //printf("%i\n",i);
            //poslednji=i+k-1;
            vector<int>temp={ind[0]};
            for(int j=i,ct=1;j<min(i+k-1,n);j++){
                temp.pb(j);
                temp.pb(ind[ct++]);
            }
            //for(auto j:temp) printf("%i ",j);printf("\n");
            int x=use_machine(temp);
            //printf("%i\n",K-x);
            res+=x>>1;
        }
        //printf("%i %i\n",res,poslednji);
        /*for(int i=poslednji;i<n;i++){
            vector<int>temp={0,i};
            if(use_machine(temp)==1) a[i]=1;
            else res++;
        }*/
    }
    return res;
}

int use_machine(std::vector<int> x);

• Subtask 1: 10 / 100