제출 #830765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830765		amunduzbaev	버섯 세기 (IOI20_mushrooms)	C++17	56.78 / 100	12 ms	364 KiB

mushrooms

#include "mushrooms.h"

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

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 20'000;

int count_mushrooms(int n){
	int B = 1;
	for(int i=1;i<=N;i++){
		if(2 * i + (N + i - 1) / i < 2 * B + (N + B - 1) / B){
			B = i;
		}
	}
	
	vector<int> p[2];
	p[0].push_back(0);
	
	int last = 1;
	for(int i=1;i<n && max((int)p[0].size(), (int)p[1].size()) < B;i++){
		last++;
		if(i + 1 < n){
			last++;
			int c = use_machine({i, 0, i + 1});
			if(c == 0) p[0].push_back(i), p[0].push_back(i + 1);
			if(c == 2) p[1].push_back(i), p[1].push_back(i + 1);
			if(c == 1){
				if(use_machine({0, i})) p[1].push_back(i), p[0].push_back(i + 1);
				else p[0].push_back(i), p[1].push_back(i + 1);
			}
			i++;
			continue;
		}
		if(use_machine({0, i})) p[1].push_back(i);
		else p[0].push_back(i);
	}
	
	ar<int, 2> cc {};
	cc[0] = p[0].size(), cc[1] = p[1].size();
	bool is = 1;
	if(p[0].size() < p[1].size()) is = 0;
	
	for(int i=last;i<n;){
		int j = min(i + B - 1, n);
		
		vector<int> qq;
		
		for(int k=i;k<j;k++){
			qq.push_back(p[is ^ 1][k - i]);
			qq.push_back(k);
		}
		
		qq.push_back(p[is ^ 1].back());
		
		int c = use_machine(qq) / 2;
		
		cc[is] += c, cc[is ^ 1] += (j - i - c);
		i = j;
	}
	
	return cc[0];
}

• Subtask 1: 56.7839 / 100