Submission #825507

#	Time	Username	Problem	Language	Result	Execution time	Memory
825507		benjaminkleyn	Counting Mushrooms (IOI20_mushrooms)	C++17	54.59 / 100	9 ms	432 KiB

mushrooms

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

set<int> A, B;
bool recurse(int l, int r, bool a = true)
{
    vector<int> query(r - l + 1);
    iota(query.begin(), query.end(), l);
    int x = use_machine(query);

    if (x == query.size() - 1)
    {
        if (a)
        {
            for (int i = l; i <= r; i += 2)
                A.insert(i);
            for (int i = l + 1; i <= r; i += 2)
                B.insert(i);
            return x % 2 == 0;
        }
        else
        {
            for (int i = l; i <= r; i += 2)
                B.insert(i);
            for (int i = l + 1; i <= r; i += 2)
                A.insert(i);
            return x % 2 == 1;
        }
    }
    if (x == 0)
    {
        if (a)
        {
            for (int i = l; i <= r; i++)
                A.insert(i);
            return true;
        }
        else
        {
            for (int i = l; i <= r; i++)
                B.insert(i);
            return false;
        }
    }

    int m = (l + r) / 2;
    return recurse(m, r, recurse(l, m, a));
}

int count_mushrooms(int n)
{
    A.insert(0);
    int i = 1;
    if (n >= 160)
    {
        recurse(0, 159);
        i = 160;
    }

    int cnt = A.size();
    while (i < n)
    {
        vector<int> query;
        if (A.size() >= B.size())
        {
            for (int j : A)
            {
                query.push_back(j);
                query.push_back(i++);
                if (i >= n)
                    break;
            }
            int x = use_machine(query);
            cnt += query.size() / 2 - (x + 1) / 2;
            if (x % 2)
                B.insert(query.back());
            else
                A.insert(query.back());
        }
        else
        {
            for (int j : B)
            {
                query.push_back(j);
                query.push_back(i++);
                if (i >= n)
                    break;
            }
            int x = use_machine(query);
            cnt += (x + 1) / 2;
            if (x % 2)
                A.insert(query.back());
            else
                B.insert(query.back());
        }
    }
    return cnt;
}

Compilation message (stderr)

mushrooms.cpp: In function 'bool recurse(int, int, bool)':
mushrooms.cpp:12:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (x == query.size() - 1)
      |         ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 54.5894 / 100