Submission #823925

#	Time	Username	Problem	Language	Result	Execution time	Memory
823925		drdilyor	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	92 ms	336 KiB

mushrooms

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

int count_mushrooms(int n) {
    vector<int> t(n);
    t[1] = use_machine({0, 1});
    if (n == 2) return 2 - t[1] - t[0];
    t[2] = use_machine({0, 2});
    bool inv = false;
    int cmp1, cmp2;
    if (t[1] && t[2]) {
        cmp1 = 1;
        cmp2 = 2;
        inv = true;
        t[0] ^= 1;
        t[1] ^= 1;
        t[2] ^= 1;
    } else {
        cmp1 = 0;
        if (!t[1]) cmp2 = 1;
        else cmp2 = 2;
    }


    for (int i = 3; i < n-1; i += 2) {
        int res = use_machine({cmp1, i, cmp2, i+1});
        t[i] = res / 2;
        t[i+1] = res % 2;
    }

    if (inv) for (int& i : t) i ^= 1;
    if (n % 2 == 0) t[n-1] = use_machine({0, n-1});

    return n - accumulate(t.begin(), t.end(), 0);
}

• Subtask 1: 25 / 100