Submission #1313561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313561		PlayVoltz	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	0 ms	400 KiB

mushrooms

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

const int X=120;

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

int count_mushrooms(int n){
	int p=1, ans=0;
	vector<int> a(1, 0), b;
	while (a.size()<X&&b.size()<X&&p<n){
		if (a.size()>b.size()){
			vector<int> temp, got;
			int m=1, c=1;
			while (2*c<=a.size()&&p+m<n)c*=2, ++m;
			for (int i=0; i<m; ++i)got.pb(p), ++p;
			int id=0;
			--m;
			for (int i=0; i<got.size()-1; ++i){
				--m;
				for (int j=0; j<(1<<m); ++j)temp.pb(a[id]), ++id, temp.pb(got[i]);
			}
			temp.pb(a[id]);
			temp.pb(got.back());
			int res=use_machine(temp);
			reverse(got.begin(), got.end());
			for (int i=0; i<got.size(); ++i){
				if (res&(1<<i))b.pb(got[i]);
				else a.pb(got[i]);
			}
		}
		else{
			vector<int> temp, got;
			int m=1, c=1;
			while (2*c<=b.size()&&p+m<n)c*=2, ++m;
			for (int i=0; i<m; ++i)got.pb(p), ++p;
			int id=0;
			--m;
			for (int i=0; i<got.size()-1; ++i){
				--m;
				for (int j=0; j<(1<<m); ++j)temp.pb(b[id]), ++id, temp.pb(got[i]);
			}
			temp.pb(b[id]);
			temp.pb(got.back());
			int res=use_machine(temp);
			reverse(got.begin(), got.end());
			for (int i=0; i<got.size(); ++i){
				if (res&(1<<i))a.pb(got[i]);
				else b.pb(got[i]);
			}
		}
	}
	if (a.size()>=X){
		while (p<n){
			vector<int> temp;
			for (int i=0; i<X&&p<n; ++i)temp.pb(a[i]), temp.pb(p), ++p;
			int res=use_machine(temp);
			ans+=temp.size()/2-(res/2+res%2);
		}
	}
	else{
		while (p<n){
			vector<int> temp;
			for (int i=0; i<X&&p<n; ++i)temp.pb(b[i]), temp.pb(p), ++p;
			int res=use_machine(temp);
			ans+=res/2+res%2;
		}
	}
	return ans+a.size();
}

• Subtask 1: 0 / 100