Submission #979282

#	Time	Username	Problem	Language	Result	Execution time	Memory
979282		Zicrus	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	71 ms	852 KiB

mushrooms

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

typedef long long ll;

int kVal, kA, kB;

void get(vector<ll> &m, int a, int b) {
    ll sol = use_machine({kA, a, kB, b});
    m[a] = (sol >> 1) ^ kVal;
    m[b] = (sol & 1) ^ kVal;
}

int count_mushrooms(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    vector<ll> m(n, 0);
    m[0] = 1;
	ll sol01 = use_machine({0, 1});
    ll sol02;
    if (n <= 2) {
        if (sol01 == 0) m[1] = 1;
        goto end; // Hello
    }
    sol02 = use_machine({0, 2});
    if (sol01 == 0) m[1] = 1;
    if (sol02 == 0) m[2] = 1;
    if (sol01 == 0) {
        kVal = 1;
        kA = 0; kB = 1;
    }
    else if (sol02 == 0) {
        kVal = 1;
        kA = 0; kB = 2;
    }
    else {
        kVal = 0;
        kA = 1; kB = 2;
    }
    for (ll i = 3; i < n-1; i += 2) {
        get(m, i, i+1);
    }
    if (!(n & 1)) {
        if (use_machine({0, n-1}) == 0) m[n-1] = 1;
    }

end:
    ll res = 0;
    for (auto &e : m) {
        res += e;
    }
    return res;
}

• Subtask 1: 25 / 100