Submission #1181085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181085		guagua0407	Counting Mushrooms (IOI20_mushrooms)	C++20	44.84 / 100	3 ms	432 KiB

mushrooms

#include "mushrooms.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    int B=205;
}

int count_mushrooms(int n) {
    B=min(B,n);
	vector<int> zero,one;
	zero.push_back(0);
	int i;
    for(i=1;i<n and (int)zero.size()<B and (int)one.size()<B;i++){
        vector<int> vec={0,i};
        int res=use_machine(vec);
        if(res==0) zero.push_back(i);
        else one.push_back(i);
    }
    int ans=(int)zero.size();
    for(;i<n;i+=B){
        int r=min(n,i+B);
        vector<int> vec;
        int cnt=0;
        for(int j=i;j<r;j++){
            if((int)zero.size()==B) vec.push_back(zero[cnt]);
            else vec.push_back(one[cnt]);
            cnt++;
            vec.push_back(j);
        }
        int res=use_machine(vec);
        if((int)zero.size()==B) ans+=(cnt-(res+1)/2);
        else ans+=(res+1)/2;
    }
	return ans;
}

• Subtask 1: 44.8413 / 100