제출 #776055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776055		boris_mihov	Counting Mushrooms (IOI20_mushrooms)	C++17	56.08 / 100	9 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 BUCKET_SIZE = 120;
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;
        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++;
    }

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

    int ans = 0;
    if (a.size() == BUCKET_SIZE)
    {
        std::vector <int> next;
        while (ptr < n)
        {
            if (next.size() == BUCKET_SIZE)
            {
                std::vector <int> toAsk;
                for (int i = 0 ; i < BUCKET_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 += BUCKET_SIZE;
                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 a.size() + ans;
    } else
    {
        assert(b.size() == BUCKET_SIZE);
        std::vector <int> next;
        while (ptr < n)
        {
            if (next.size() == BUCKET_SIZE)
            {
                std::vector <int> toAsk;
                for (int i = 0 ; i < BUCKET_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;
                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 a.size() + ans;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:86:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int i = 0 ; i < next.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~
mushrooms.cpp:137:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for (int i = 0 ; i < next.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~

• Subtask 1: 56.0794 / 100