제출 #429984

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

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
struct segTree{
	int dd, htt, val, mid;
	segTree *L, *R;
	segTree(int l, int r, int vale){
		dd=l, htt=r;
		mid=(dd+htt)/2;
		if(vale!=-1)val=vale;
		else{
			vector<int>temp;
			for(int i = dd; i<= htt ; i++){
				temp.PB(i);
			}
			val=use_machine(temp);
			
		}
		//cout<<dd<<" "<<htt<<" "<<val<<endl;
		if(val==0||val==(htt-dd)){
		}else{
			if(l+1<r){
				L = new segTree(l, mid, -1);
				R = new segTree(mid, r, val-L->val);
			}
		}
	}
	int ask(int l, int r){
		if(val==0){
			return 0;
		}
		if(val==(htt-dd)){
			return 1;
		}
		if(l==dd&&r==htt)return val;
		if(r<=mid){
			return L->ask(l , r);
		}else{
			return R->ask(l, r);
		}
	}
};
int count_mushrooms(int n) {
	vector<int> rta, m;
	int fin = 0;
	rta.PB(0);
	segTree *tree = new segTree(0, n-1, -1);
	for(int i = 0 ; i < n-1 ; i++){
		if(rta.back()==0)fin++;
		int ans;
		//m.PB(i), m.PB(i+1);
		ans = tree->ask(i, i+1);
		if(ans){
			rta.PB(abs(rta.back()-1));
		}else{
			rta.PB(rta.back());
		}
		m.pop_back();
		m.pop_back();
	}
	if(rta.back()==0)fin++;
	return fin;
}

• Subtask 1: 0 / 100