Submission #558370

#	Time	Username	Problem	Language	Result	Execution time	Memory
558370		ymm	버섯 세기 (IOI20_mushrooms)	C++17	91.87 / 100	9 ms	452 KiB

mushrooms

///
///   Standing here
///   I realize
///   You are just like me
///   Trying to make history
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#ifndef LOCAL
#include "mushrooms.h"
#else
int count_mushrooms(int n);
const int a[] = {0, 1, 0, 0};
const int n = sizeof(a)/sizeof(a[0]);
int use_machine(vector<int> v)
{
	int ans = 0;
	Loop (i,0,v.size()-1)
		ans += a[v[i]] != a[v[i+1]];
	return ans;
}
int main()
{
	int ans = 0;
	Loop (i,0,n) ans += !a[i];
	cout << ans << '\n';
	cout << count_mushrooms(n) << '\n';
}
#endif


int count_mushrooms(int n) {
	vector<int> known[2];
	known[0].push_back(0);
	int p = 1;
	int ans = 1;
	while (p < n) {
		int c = known[0].size() < known[1].size();
		int x = known[c].size();
		if (x < 60 && x > 1)
			x = 2;
		x = min(x, n - p);
		vector<int> vec;
		Loop (i,0,x) {
			vec.push_back(known[c][i]);
			vec.push_back(p+i);
		}
		int y = use_machine(vec);
		known[(y&1)^c].push_back(p+x-1);
		if (x == 2)
			known[(y>>1)^c].push_back(p);
		ans += c? (y+1)/2: x - (y+1)/2;
		p += x;
	}
	return ans;
}

• Subtask 1: 91.8699 / 100