Submission #772423

#	Time	Username	Problem	Language	Result	Execution time	Memory
772423		t6twotwo	Counting Mushrooms (IOI20_mushrooms)	C++17	79.58 / 100	13 ms	512 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int N) {
    if (N == 2) {
        return 2 - use_machine({0, 1});
    }
    vector<int> p(N);
    iota(p.begin(), p.end(), 0);
    for (int i = 0; i < 2; i++) {
        shuffle(p.begin(), p.end(), rng);
        use_machine(p);
    }
    int A = use_machine({0, 1});
    int B = use_machine({0, 2});
    int C = 0;
    vector<int> T[2];
    T[0].push_back(0);
    T[A].push_back(1);
    T[B].push_back(2);
    if (A == 0) {
        A = 0;
        B = 1;
    } else if (B == 0) {
        A = 0;
        B = 2;
    } else {
        A = 1;
        B = 2;
        C = 1;
    }
    int i = 3;
    for (; i + 1 < N && i <= 281; i += 2) {
        int x = use_machine({A, i, B, i + 1});
        T[C ^ (x > 1)].push_back(i);
        T[C ^ (x % 2)].push_back(i + 1);
    }
    if (T[0].size() > T[1].size()) {
        C = 0;
    } else {
        C = 1;
    }
    int M = T[C].size(), ans = T[0].size();
    for (; i < N;) {
        int K = min(N - i, M - 1);
        vector<int> v;
        for (int j = 0; j < K; j++) {
            v.push_back(T[C][j]);
            v.push_back(i++);
        }
        v.push_back(T[C][K]);
        int x = use_machine(v) / 2;
        if (C) {
            ans += x;
        } else {
            ans += K - x;
        }
    }
    return ans;
}

• Subtask 1: 79.5775 / 100