제출 #592335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592335		farhan132	버섯 세기 (IOI20_mushrooms)	C++17	0 / 100	2 ms	208 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

int count_mushrooms(int n) {
	ll ans = 1;
	
	if(n <= 226){
		for(ll i = 1; i < n; i++){
			ans += 1 - use_machine({0, i});
		}
		return ans;
	}

	vector < ll > done(n + 100, 0);
	vector < ll > A, B;
	A.pb(0);
	ll N = 200;
	for(ll i = 1; i <= 2; i++){
		if(1 - use_machine({0, i})) A.pb(i), ans++;
		else B.pb(i), ans++;
	}
	for(ll i = 3; i <= N; i+=2){
		if(A.size() > B.size()){
			ll k = use_machine({A[0], i, A[1], i + 1});
			if(k == 0) A.pb(i), A.pb(i + 1), ans+=2;
			if(k == 1) A.pb(i), B.pb(i + 1), ans++;
			if(k == 2) B.pb(i), A.pb(i + 1), ans++;
			if(k == 3) B.pb(i), B.pb(i + 1); 
		}else{
			ll k = use_machine({B[0], i, B[1], i + 1});
			if(k == 3) A.pb(i), A.pb(i + 1), ans += 2;
			if(k == 2) A.pb(i), B.pb(i + 1), ans++;
			if(k == 1) B.pb(i), A.pb(i + 1), ans++;
			if(k == 0) B.pb(i), B.pb(i + 1); 
		}
	}
	ll sz; bool f = 0;
	if(B.size() > A.size()) f = 1, sz = B.size();
	else sz = A.size();
	for(ll i = N+1; i + sz - 1 < n; i+=sz){
		if(!f){
			vector < ll > cur;
			cur.pb(A[0]); ll p = i, q = 0;
			for(ll j = 1; j < sz; j++){
				done[p] = 1;
				cur.pb(p);
				cur.pb(A[j]);
				p++;
				q++;
				if(p == n) break;
			}
			ll k = use_machine(cur);
			ans += (q) - (k/2);
		}else{
			vector < ll > cur;
			cur.pb(B[0]); ll p = i, q = 0;
			for(ll j = 1; j < sz; j++){
				done[p] = 1;
				cur.pb(p);
				cur.pb(B[j]);
				p++;
				q++;
				if(p == n) break;
			}
			ll k = use_machine(cur);
			ans += (k/2);
		}
	}
	
	return ans;
}

• Subtask 1: 0 / 100