Submission #773675

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

mushrooms

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

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:17:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   17 |     T[x >> 1 & 1 ^ z].push_back(i++);
      |       ~~~~~~~^~~
mushrooms.cpp:18:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   18 |     T[x >> 0 & 1 ^ z].push_back(i++);
      |       ~~~~~~~^~~
mushrooms.cpp:22:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   22 |         T[x & 1 ^ z].push_back(i++);
      |           ~~^~~
mushrooms.cpp:24:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   24 |             T[x >> 2 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:25:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   25 |             T[x >> 2 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:34:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   34 |         T[x & 1 ^ z].push_back(i++);
      |           ~~^~~
mushrooms.cpp:36:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   36 |             T[x >> 2 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:37:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   37 |             T[x >> 2 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:40:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   40 |             T[x >> 2 & 1 ^ z ^ 1].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:41:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   41 |             T[x >> 2 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:42:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   42 |             T[x >> 1 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:43:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   43 |             T[x >> 0 & 1 ^ z].push_back(i++);
      |               ~~~~~~~^~~
mushrooms.cpp:61:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   61 |         T[x & 1 ^ z].push_back(i - 1);
      |           ~~^~~

• Subtask 1: 100 / 100