Submission #772524

#	Time	Username	Problem	Language	Result	Execution time	Memory
772524		t6twotwo	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	7 ms	444 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int N) {
    if (N == 2) {
        return 2 - use_machine({0, 1});
    }
    vector<int> T[] = {{0}, {}};
    T[use_machine({0, 1})].push_back(1);
    T[use_machine({0, 2})].push_back(2);
    int i = 3;
    for (int z = T[1].size() > 1; i + 1 < N && i <= 141; i += 2) {
        int x = use_machine({T[z][0], i, T[z][1], i + 1});
        T[z ^ (x > 1)].push_back(i);
        T[z ^ (x % 2)].push_back(i + 1);
    }
    int ans = T[0].size();
    while (i < N) {
        int z = T[1].size() > T[0].size();
        int K = min(N - i, (int)T[z].size());
        vector<int> v;
        for (int j = 0; j < K; j++) {
            v.push_back(T[z][j]);
            v.push_back(i++);
        }
        int x = use_machine(v);
        if (z) {
            ans += x / 2 + x % 2;
        } else {
            ans += K - x / 2 - x % 2;
        }
        T[z ^ x & 1].push_back(i - 1);
    }
    return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:32:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   32 |         T[z ^ x & 1].push_back(i - 1);
      |               ~~^~~

• Subtask 1: 92.2449 / 100