Submission #776075

#	Time	Username	Problem	Language	Result	Execution time	Memory
776075		boris_mihov	Counting Mushrooms (IOI20_mushrooms)	C++17	88.98 / 100	8 ms	476 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 = 100;
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]);

    while (ptr < n && a.size() < BUCKET_SIZE && b.size() < BUCKET_SIZE)
    {
        std::vector <int> curr;
        if (ptr + 1 == n || (a.size() <= 1 && b.size() <= 1))
        {
            curr.push_back(order[0]);
            curr.push_back(order[ptr]);
            int res = use_machine(curr);

            if (res == 0)
            {
                a.push_back(order[ptr]);
            } else
            {
                b.push_back(order[ptr]);
            }
        
            ptr++;
        } else
        {
            if (a.size() >= 2)
            {
                curr.push_back(a[0]);
                curr.push_back(order[ptr]);
                curr.push_back(a[1]);
                curr.push_back(order[ptr + 1]);
                int res = use_machine(curr);

                if (res & 1) b.push_back(order[ptr + 1]);
                else a.push_back(order[ptr + 1]);

                if (res & 2) b.push_back(order[ptr]);
                else a.push_back(order[ptr]);
                ptr += 2;
            } else
            {
                curr.push_back(b[0]);
                curr.push_back(order[ptr]);
                curr.push_back(b[1]);
                curr.push_back(order[ptr + 1]);
                int res = use_machine(curr);

                if (res & 1) a.push_back(order[ptr + 1]);
                else b.push_back(order[ptr + 1]);

                if (res & 2) a.push_back(order[ptr]);
                else b.push_back(order[ptr]);
                ptr += 2;
            }
        }
    }

    if (ptr == n)
    {
        return a.size();
    }

    int ans = a.size();
    if (a.size() >= BUCKET_SIZE)
    {
        std::vector <int> next;
        while (ptr < n)
        {
            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:95:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for (int i = 0 ; i < a.size() ; ++i)
      |                                  ~~^~~~~~~~~~
mushrooms.cpp:125:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             for (int i = 0 ; i < next.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~
mushrooms.cpp:152:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |                 for (int i = 0 ; i < b.size() ; ++i)
      |                                  ~~^~~~~~~~~~
mushrooms.cpp:179:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             for (int i = 0 ; i < next.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~

• Subtask 1: 88.9764 / 100