Submission #322270

#	Time	Username	Problem	Language	Result	Execution time	Memory
322270		grt	Counting Mushrooms (IOI20_mushrooms)	C++17	91.87 / 100	10 ms	496 KiB

mushrooms

#include <bits/stdc++.h>
 
using namespace std;
 
using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;
 
#define ST first
#define ND second
#define PB push_back
 
const int B = 65;
vi a, b;
 
int use_machine(vi x);
 
int count_mushrooms(int n) {
    srand(time(NULL));
    if(n == 1) return 1;
    vi v(n-1);
    a = {};
    b = {};
    for(int i = 1; i < n; ++i) v[i - 1] = i;
    random_shuffle(v.begin(), v.end());
    a.PB(0);
    for(int i = 0; i < min(n - 1, 2); ++i) {
        int w = use_machine({0, v[i]});
        if(w == 1) b.PB(v[i]);
        else a.PB(v[i]);
    }
    int ans = (int)a.size();
    bool inv = 0;
    if((int)b.size() > (int)a.size()) {
		swap(a, b);
		inv = 1;
	}
    for(int i = 2; i < n - 1; i++) {
		vi s = {};
		bool typ = 0;
		int nxt = 0, all = 0;
		int last = 0;
		if((int)a.size() < B) {
			typ = 1;
			for(int j = i; j < min(n - 1, i + 2); ++j) {
				s.PB(a[nxt++]);
				s.PB(v[j]);
				all++;
				last = j;
			}
		} else {
			for(int j = i; j < min(n - 1, i + (int)a.size()); ++j) {
				s.PB(a[nxt++]);
				s.PB(v[j]);
				all++;
				last = j;
			}
		}
        int w = use_machine(s);
        if(!inv) {
            int cntB = w / 2 + (w % 2);
            ans += all - cntB;
            if(w%2 == 0) {
                a.PB(v[last]);
            } else {
                b.PB(v[last]);
            }
            if(typ) {
				if(w >= 2 && last > 0) b.PB(v[last - 1]);
				else if(last > 0) a.PB(v[last - 1]);
			}
        } else {
            ans += w/2 + (w%2);
            if(w % 2 == 0) {
                a.PB(v[last]);
            } else {
                b.PB(v[last]);
            }
            if(typ) {
				if(w >= 2 && last > 0) b.PB(v[last - 1]);
				else if(last > 0) a.PB(v[last - 1]);
			}
        }
        if((int)b.size() > (int)a.size()) {
            inv = 1 - inv;
            swap(a, b);
        }
        i = last;
    }
    return ans;
}

• Subtask 1: 91.8699 / 100