Submission #771663

#	Time	Username	Problem	Language	Result	Execution time	Memory
771663		t6twotwo	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	208 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> a, p(N - 1);
    int mn = 1e9;
    iota(p.begin(), p.end(), 1);
    for (int i = 0; i < 100; i++) {
        shuffle(p.begin(), p.end(), rng);
        int x = use_machine(p);
        if (x < mn) {
            mn = x;
            swap(a, p);
        }
    }
    int ans = 1;
    for (int i = 0; i < N - 1;) {
        bool f = use_machine({0, a[i]}) == 0;
        vector<int> p{a[i]};
        if (f) {
            ans++;
        }
        if (++i == N - 1) {
            break;
        }
        for (int j = 0; ; j++) {
            if (i + (1 << j) > N - 1) {
                j = -1;
                continue;
            }
            for (int k = i; k < i + (1 << j); k++) {
                p.push_back(a[k]);
            }
            if (use_machine(p) != 0) {
                if (j == 0) {
                    break;
                }
                for (int k = 0; k < (1 << j); k++) {
                    p.pop_back();
                }
                j = -1;
            } else {
                if (f) {
                    ans += 1 << j;
                }
                i += 1 << j;
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 100