제출 #1228354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228354		Nonoze	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 ms	428 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)x.size()
using namespace std;

int n, cntcalls=0;
vector<int> A(1, 0), B;
const int LIMIT=100;

int calcone(int &i) {
	auto val=2-use_machine({i, A[0], i+1}); cntcalls++;
	if (val==2) A.pb(i), A.pb(i+1);
	else if (val==0) B.pb(i), B.pb(i+1);
	else {
		if (!use_machine({A[0], i})) A.pb(i), B.pb(i+1);
		else A.pb(i+1), B.pb(i);
		cntcalls++;
	}
	i+=2;
	return val;
}

int calcA(int &i) {
	int l=i, r=min(n-1, i+sz(A)-2);
	vector<int> m;
	for (auto &u: A) {
		if (i>=n) break;
		m.pb(u), m.pb(i++);
	}
	m.pop_back(), i-=2; while (i>=n) m.pop_back(), m.pop_back(), i--;
	i++;
	auto val=sz(m)/2 - use_machine(m)/2;
	int cnt=0;
	for (; l<r && cnt<val&&max(sz(A), sz(B))<LIMIT; l++) {
		if (sz(A)>1) {
			auto val=use_machine({l, A[0], l+1, A[1]});
			if (val==0) A.pb(l), A.pb(l+1), cnt+=2;
			else if (val==1) B.pb(l), A.pb(l+1), cnt++;
			else if (val==2) A.pb(l), B.pb(l+1), cnt++;
			else B.pb(l), B.pb(l+1);
			l++;
		} else {
			if (!use_machine({A[0], l})) A.pb(l), cnt++;
			else B.pb(l);
		}
		cntcalls++;
	}
	if (max(sz(A), sz(B))<LIMIT) {
		if (cnt<val) A.pb(l);
		else B.pb(l);
	}
	return val;
}

int calcB(int &i) {
	int l=i, r=min(n-1, i+sz(B)-2);
	vector<int> m;
	for (auto &u: B) {
		m.pb(u), m.pb(i++);
	}
	m.pop_back(), i-=2; while (i>=n) m.pop_back(), m.pop_back(), i--;
	i++;
	auto val=use_machine(m)/2; cntcalls++;
	int cnt=0;
	for (; l<r && cnt<val&&max(sz(A), sz(B))<LIMIT; l++) {
		if (sz(A)>1) {
			auto val=use_machine({l, A[0], l+1, A[1]});
			if (val==0) A.pb(l), A.pb(l+1), cnt+=2;
			else if (val==1) B.pb(l), A.pb(l+1), cnt++;
			else if (val==2) A.pb(l), B.pb(l+1), cnt++;
			else B.pb(l), B.pb(l+1);
			l++;
		} else {
			if (!use_machine({A[0], l})) A.pb(l), cnt++;
			else B.pb(l);
		}
		cntcalls++;
	}
	if (max(sz(A), sz(B))<LIMIT && l==r) {
		if (cnt<val) A.pb(l);
		else B.pb(l);
	}
	return val;
}


int count_mushrooms(int _n) { n=_n;
	int ans=1;
	for (int i=1; i<n;) {
		if (i==n-1) {
			ans+=1-use_machine({0, i});
			i++;
		} else {
			if (sz(A)>sz(B) || sz(B)<3) {
				if (sz(A)<=2) ans+=calcone(i);
				else ans+=calcA(i);
			} else {
				ans+=calcB(i);
			}
		}
	}
	return ans;
}

• Subtask 1: 0 / 100