Submission #578616

#	Time	Username	Problem	Language	Result	Execution time	Memory
578616		SlavicG	Counting Mushrooms (IOI20_mushrooms)	C++17	75.59 / 100	12 ms	720 KiB

mushrooms

#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()

int count_mushrooms(int n) {
	vector<int> a(n, -1);
	a[0] = 0;
	if(n <= 226) {
        for(int i = 1; i < n; ++i) {
            int x = use_machine({i - 1, i});
            if(x) a[i] = !a[i - 1];
            else a[i] = a[i - 1];
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) if(a[i] == 0) ++ans;
        return ans;
	}

	vector<int> A;
	vector<int> B;
	A.pb(0);
	int x = use_machine({0, 1});
	if(x == 0) A.pb(1);
	else B.pb(1);
	x = use_machine({0, 2});
	if(x == 0) A.pb(2);
	else B.pb(2);

    for(auto x: A) a[x] = 0;
    for(auto x: B) a[x] = 1;
	if(sz(A) >= 2) {
        for(int i = 3; i + 1 < min(n, 275); i += 2) {
            vector<int> v;
            v.pb(A[0]);
            v.pb(i);
            v.pb(A[1]);
            v.pb(i + 1);
            int x = use_machine(v);
            if(x & 2) {
                B.pb(i);
            } else A.pb(i);
            if(x & 1) {
                B.pb(i + 1);
            } else A.pb(i + 1);

            if(max(sz(A), sz(B)) >= 100) break;
        }
	} else {
        for(int i = 3; i + 1 < min(n, 275); i += 2) {
            vector<int> v;
            v.pb(B[0]);
            v.pb(i);
            v.pb(B[1]);
            v.pb(i + 1);
            int x = use_machine(v);
            if(x & 2) {
                A.pb(i);
            } else B.pb(i);
            if(x & 1) {
                A.pb(i + 1);
            } else B.pb(i + 1);
            if(max(sz(A), sz(B)) >= 100) break;
        }
	}

    int cnt = 0;
	for(auto x: A) {
        ++cnt;
        a[x] = 0;
	}
	for(auto x: B) a[x] = 1;
	vector<int> v;
	for(int i = 0; i < n; ++i) {
        if(a[i] == -1) v.pb(i);
	}
	if(sz(B) >= sz(A)) {
        assert(sz(B) >= 1);
        for(int i = 0; i < sz(v); i += sz(B)) {
            vector<int> f;
            int idx = 0;
            for(int j = i; j < sz(v) && j < i + sz(B); ++j) {
                f.pb(B[idx++]);
                f.pb(v[j]);
            }
            int x = use_machine(f);
            cnt += (x / 2) + (x % 2);
        }
        return cnt;
	} else {
        assert(sz(A) >= 1);
        cnt += sz(v);
        for(int i = 0; i < sz(v); i += sz(A)) {
            vector<int> f;
            int idx = 0;
            for(int j = i; j < sz(v) && j < i + sz(A); ++j) {
                f.pb(A[idx++]);
                f.pb(v[j]);
            }
            int x = use_machine(f);
            cnt -= (x / 2) + (x % 2);
        }
        return cnt;
	}
}

• Subtask 1: 75.5853 / 100