Submission #1240458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240458		Sir_Ahmed_Imran	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	68 ms	756 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 check(vector<int> m){
	if(m.size() == 1)
		return 0;
	return use_machine(m);
}

int count(int l, int r, int val){
	if(!val){
		if(check({0, v[l]}) == 0)
			return r - l;
		return 0;
	}
	if(val == r - l - 1){
		if(check({0, v[l]}))
			return (r - l) / 2;
		return (r - l + 1) / 2;
	}
	int x = (r - l) / (min(val, r - l - 1 - val) + 1);
	x = max(x, 2);
	random_device rd;
    mt19937 g(rd());
    shuffle(v + l, v + r, g);
    int ans = 0;
    vector<int> m;
    for(int i = l; i < r; i++){
    	if(m.size() == x){
    		ans += count(l, i, check(m));
    		m.clear();
    		l = i;
    	}
    	m.append(v[i]);
    }
    if(!m.empty())
    	ans += count(l, r, check(m));
    return ans;
}

int count_mushrooms(int n) {
	vector<int> m;
	for(int i = 1; i < n; i++){
		m.append(i);
		v[i] = i;
	}
	return count(1, n, check(m)) + 1;
}

• Subtask 1: 10 / 100