Submission #800091

#	Time	Username	Problem	Language	Result	Execution time	Memory
800091		boris_mihov	버섯 세기 (IOI20_mushrooms)	C++17	0 / 100	1 ms	208 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]);
 
    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();
    }
 
    std::vector <int> next;
    int ans = a.size();
    while (ptr < n)
    {
        if (a.size() >= BUCKET_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--;
                } else
                {
                    a.push_back(toAsk.back());
                    decr = true;
                }

                ans -= res >> 1;
                ans += a.size() - decr;
                next.clear();
            } else
            {
                next.push_back(order[ptr++]);
            }
        } 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() && 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: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:129:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                     for (int i = 0 ; i < b.size() ; ++i)
      |                                      ~~^~~~~~~~~~
mushrooms.cpp:158:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for (int i = 0 ; i < next.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~
mushrooms.cpp:178:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for (int i = 0 ; i < next.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 100