Submission #776029

#	Time	Username	Problem	Language	Result	Execution time	Memory
776029		boris_mihov	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	133 ms	464 KiB

mushrooms

#include "mushrooms.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>

typedef long long llong;
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) 
{
    for (int i = 0 ; i <= n ; ++i)
    {
        min[i] = n;
        max[i] = 0;
    }

    order.resize(n);
    std::iota(order.begin(), order.end(), 0);
    std::shuffle(order.begin() + 1, order.end(), rng);

    int ans = 0;
    int ptr = 0;
    int last = -1;
    while (true)
    {
        int l = max[ptr], r = min[ptr + 1], mid;

        int pw = -1;
        while (l + (1 << pw + 1) < r)
        {
            std::vector <int> toAsk(order.begin() + max[ptr], order.begin() + l + (1 << pw + 1) + 1);
            int res = use_machine(toAsk);
            min[ptr + res] = std::min(min[ptr + res], l + (1 << pw + 1));
            max[ptr + res] = std::max(max[ptr + res], l + (1 << pw + 1));

            if (res == 0) pw++;
            else 
            {
                break;
            }
        }

        l = l + (pw == -1 ? 0 : (1 << pw));
        r = std::min(r, l + (1 << pw + 1));

        while (l < r - 1)
        {
            mid = (l + r) / 2;
            std::vector <int> toAsk(order.begin() + max[ptr], order.begin() + mid + 1);
            int res = use_machine(toAsk);
            min[ptr + res] = std::min(min[ptr + res], mid);
            max[ptr + res] = std::max(max[ptr + res], mid);

            if (res == 0) l = mid;
            else r = mid;
        }

        if (ptr % 2 == 0)
        {
            ans += l - last;
        }

        assert(min[ptr + 1] == max[ptr] + 1);
        if (max[ptr] == n - 1)
        {
            break;
        }

        last = l;
        ptr++;
    }

    return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:38:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   38 |         while (l + (1 << pw + 1) < r)
      |                          ~~~^~~
mushrooms.cpp:40:92: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   40 |             std::vector <int> toAsk(order.begin() + max[ptr], order.begin() + l + (1 << pw + 1) + 1);
      |                                                                                         ~~~^~~
mushrooms.cpp:42:68: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 |             min[ptr + res] = std::min(min[ptr + res], l + (1 << pw + 1));
      |                                                                 ~~~^~~
mushrooms.cpp:43:68: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 |             max[ptr + res] = std::max(max[ptr + res], l + (1 << pw + 1));
      |                                                                 ~~~^~~
mushrooms.cpp:53:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   53 |         r = std::min(r, l + (1 << pw + 1));
      |                                   ~~~^~~

• Subtask 1: 0 / 100