제출 #1240392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240392		Sir_Ahmed_Imran	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	16 ms	768 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 20000
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int v[MAXN];

int get(int l, int r){
	if(r - l == 1)
		return 0;
	vector<int> m;
	for(int i = l; i < r; i++)
		m.append(v[i]);
	return use_machine(m);
}

int count(int l, int r){
	int val = get(l, r);
	if(!val){
		if(use_machine({0, v[l]}))
			return 0;
		return r - l;
	}
	if(val == r - l - 1){
		if(use_machine({0, v[l]}))
			return (r - l) / 2;
		return (r - l + 1) / 2;
	}
	int mid = (l + r) / 2;
	random_device rd;
    mt19937 g(rd());
    shuffle(v + l, v + r, g);
    return count(l, mid) + count(mid, r);
}

int count_mushrooms(int n) {
	for(int i = 0; i < n; i++)
		v[i] = i;
	return count(1, n) + 1;
}

• Subtask 1: 0 / 100