Submission #1320488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320488		BigBadBully	Rarest Insects (IOI22_insects)	C++20	47.51 / 100	65 ms	592 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int n) {
    int dst = 0;
    vector<int> gurt(n);
    for(int i = 0; i < n; i++)
        gurt[i] = i;
    srand(time(0));
    random_shuffle(gurt.begin(),gurt.end());
    set<int> dists;
    {
    set<int> hier;
    for (int i :gurt)
    {
        move_inside(i);
        int val = press_button();
        if(val>1)
            move_outside(i);
        else
            dst++,dists.insert(i),hier.insert(i);
        
    }
    for(int x: hier)
        if(!dists.count(x))
            move_outside(x);
    }
    vector<int> lst(n,0);
    function<bool(int)> check = [&](int x)
    {
        if(x>n)return true;
        if(x==0)return false;
        int sz = dst;
        set<int> hier;
        for(int i :gurt)
        {
            if(dists.count(i) || lst[i]>=x)continue;
            move_inside(i);
            int val = press_button();
            if(val>x)
                move_outside(i),lst[i] = max(lst[i],x);
            else
                sz++,hier.insert(i);
        }
        for(int y: hier)
            if(!dists.count(y))
            move_outside(y);
        return sz < x*dst;
    };
    int l = 1,r = n/dst;
    while(r-l)
    {
        int mid = l+r+1>>1;
        if(check(mid))
            r = mid-1;
        else
            l = mid;
    }
    return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:11:19: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   11 |     random_shuffle(gurt.begin(),gurt.end());
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from insects.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 22.51 / 75