제출 #1240409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240409		Sir_Ahmed_Imran	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	8 ms	732 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 == 0){
		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;
	}
	if(r - l < 50){
		int ans = 0;
		for(int i = l + 1; i < r; i += 2)
			ans += count(i - 1, i + 1);
		if((l + r) % 2)
			ans += count(r - 1, r);
		return ans;
	}
	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