Submission #800101

#	Time	Username	Problem	Language	Result	Execution time	Memory
800101		boris_mihov	Counting Mushrooms (IOI20_mushrooms)	C++17	80.71 / 100	8 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
 
typedef long long llong;
const int BUCKET_SIZE = 3; //110;
const int MAXN = 100000 + 10;
const int INF  = 1e9;
 
int min[MAXN];
int max[MAXN];
std::vector <int> order;
std::mt19937 rng(69420);
 
int count_mushrooms(int n) 
{
    order.resize(n);
    std::iota(order.begin(), order.end(), 0);
    std::shuffle(order.begin() + 1, order.end(), rng);
 
    int ptr = 1;
    std::vector <int> a, b;
    a.push_back(order[0]);
    
    std::vector <int> next;
    int ans = a.size();
    while (ptr < n)
    {
        if (a.size() > b.size())
        {
            if (next.size() == a.size())
            {
                std::vector <int> toAsk;
                for (int i = 0 ; i < a.size() ; ++i)
                {
                    toAsk.push_back(a[i]);
                    toAsk.push_back(next[i]);
                }

                int res = use_machine(toAsk);
                bool decr = false;
                if (res & 1)
                {
                    ans--;
                    res--;
                    b.push_back(toAsk.back());
                } else
                {
                    a.push_back(toAsk.back());
                    decr = true;
                }

                ans -= res >> 1;
                ans += a.size() - decr;
                next.clear();
            } else
            {
                next.push_back(order[ptr++]);
            }
        } else
        {
            if (next.size() == b.size())
            {
                std::vector <int> toAsk;
                for (int i = 0 ; i < b.size() ; ++i)
                {
                    toAsk.push_back(b[i]);
                    toAsk.push_back(next[i]);
                }

                int res = use_machine(toAsk);
                if (res & 1)
                {
                    ans++;
                    res--;
                    a.push_back(toAsk.back());
                } else
                {
                    b.push_back(toAsk.back());
                }

                ans += res >> 1;
                next.clear();
            } else
            {
                next.push_back(order[ptr++]);
            }
        }
    }

    if (next.size() && a.size() > b.size())
    {
        std::vector <int> toAsk;
        for (int i = 0 ; i < next.size() ; ++i)
        {
            toAsk.push_back(a[i]);
            toAsk.push_back(next[i]);
        }

        int res = use_machine(toAsk);
        if (res & 1)
        {
            ans--;
            res--;
        }

        ans -= res >> 1;
        ans += next.size();
    }

    if (next.size() && b.size() >= a.size())
    {
        std::vector <int> toAsk;
        for (int i = 0 ; i < next.size() ; ++i)
        {
            toAsk.push_back(b[i]);
            toAsk.push_back(next[i]);
        }

        int res = use_machine(toAsk);
        if (res & 1)
        {
            ans++;
            res--;
        }

        ans += res >> 1;
    }

    return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:38:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 for (int i = 0 ; i < a.size() ; ++i)
      |                                  ~~^~~~~~~~~~
mushrooms.cpp:69:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 for (int i = 0 ; i < b.size() ; ++i)
      |                                  ~~^~~~~~~~~~
mushrooms.cpp:98:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = 0 ; i < next.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~
mushrooms.cpp:118:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i = 0 ; i < next.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~

• Subtask 1: 80.7143 / 100