제출 #424272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
424272		Apiram	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	1 ms	200 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int solve1(int left ,int right,int k);
int solve2(int left ,int right,int k){
	if (left>right)return 0;
	if (left==right){
		int a=use_machine({0,left});
		if (a==0)return 1;
		else return 0;
	}
	vector<int>arr;
	for (int i =left;i<=right;++i)arr.push_back(i);
	int a = use_machine(arr);
	int temp = a;
	int counts=0;
	if (a==(k+1)/2){
		a= use_machine({0,left});
		if (a==0)counts++;
	}
	left++;
	int mid = (left+right)/2;
	return solve1(left,mid,temp) + solve2(mid+1,right,temp)+counts;
	
}
int solve1(int left ,int right,int k){
	if (left>right)return 0;
	if (left==right){
		int a=use_machine({0,left});
		if (a==0)return 1;
		else return 0;
	}
	vector<int>arr;
	for (int i =left;i<=right;++i)arr.push_back(i);
	int a = use_machine(arr);
	int temp = a;
	int counts=0;
	if (a==(k+1)/2){
		a= use_machine({0,right});
		if (a==0)counts++;
	}
	else counts++;
	right--;
	int mid = (left+right)/2;
	return solve1(left,mid,temp) + solve2(mid+1,right,temp) + counts;
	
}
int count_mushrooms(int n) {
	vector<int>arr(n-1);
	iota(arr.begin(),arr.end(),1);
	int a= use_machine(arr);
	int left = 1;
	int right = n-1;
	int mid = (left + right) >>1; 
	return solve1(1,mid,a) + solve2(mid+1,right,a)+1;
}

• Subtask 1: 0 / 100