Submission #776020

#	Time	Username	Problem	Language	Result	Execution time	Memory
776020		boris_mihov	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	12 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 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;
        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;
}

• Subtask 1: 0 / 100