Submission #800086

#	Time	Username	Problem	Language	Result	Execution time	Memory
800086		boris_mihov	Counting Mushrooms (IOI20_mushrooms)	C++17	Compilation error	0 ms	0 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 = 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]);
    int ans = a.size();
    while (ptr < n)
    {
        if (a.size() >= BUCKET_SIZE)
        {
            std::vector <int> next;
            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--;
                } else
                {
                    a.push_back(toAsk.back());
                    decr = true;
                }

                ans -= res >> 1;
                ans += a.size() - decr;
                next.clear();
            } else
            {
                next.push_back(order[ptr++]);
            }
        }
        
        if (next.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();
        }

        return ans;
    } else
    {
        assert(b.size() >= BUCKET_SIZE);
        std::vector <int> next;
        while (ptr < n)
        {
            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--;
                } else
                {
                    b.push_back(toAsk.back());
                }

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

        if (next.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:37:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 for (int i = 0 ; i < a.size() ; ++i)
      |                                  ~~^~~~~~~~~~
mushrooms.cpp:64:13: error: 'next' was not declared in this scope; did you mean 'std::next'?
   64 |         if (next.size())
      |             ^~~~
      |             std::next
In file included from /usr/include/c++/10/bits/stl_algobase.h:66,
                 from /usr/include/c++/10/vector:60,
                 from mushrooms.h:1,
                 from mushrooms.cpp:1:
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:213:5: note: 'std::next' declared here
  213 |     next(_InputIterator __x, typename
      |     ^~~~
mushrooms.cpp:85:7: error: 'else' without a previous 'if'
   85 |     } else
      |       ^~~~
mushrooms.cpp:94:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                 for (int i = 0 ; i < b.size() ; ++i)
      |                                  ~~^~~~~~~~~~
mushrooms.cpp:121:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for (int i = 0 ; i < next.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~