Submission #628597

#	Time	Username	Problem	Language	Result	Execution time	Memory
628597		Sorting	Rarest Insects (IOI22_insects)	C++17	87.59 / 100	92 ms	404 KiB

insects

#include "insects.h"
#include <vector>
#include <random>
#include <algorithm>
#include <set>

using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

const int C = 4;

int min_cardinality(int n) {
    vector<int> v;
    v.push_back(0);
    move_inside(0);
    for(int i = 1; i < n; ++i){
        move_inside(i);
        if(press_button() == 2){
            move_outside(i);
        }
        else
            v.push_back(i);
    }

    for(int x: v)
        move_outside(x);
    
    vector<int> type(n);

    int k = v.size();
    if(k <= C){
        vector<bool> in_v(n, false);
        for(int x: v)
            in_v[x] = true;

        for(int i = 0; (1 << i) < k; ++i){
            for(int j = 0; j < k; ++j){
                if((j >> i) & 1){
                    type[v[j]] += (1 << i);
                    move_inside(v[j]);
                }
            }
            for(int j = 0; j < n; ++j){
                if(in_v[j]) continue;
                move_inside(j);
                if(press_button() == 2)
                    type[j] += (1 << i);
                move_outside(j);
            }
            for(int j = 0; j < k; ++j){
                if((j >> i) & 1){
                    move_outside(v[j]);
                }
            }
        }
        vector<int> cnt(k);
        for(int i = 0; i < n; ++i)
            cnt[type[i]]++;

        return *min_element(cnt.begin(), cnt.end());
    }

    vector<int> rem;
    for(int i = 0; i < n; ++i){
        if(find(v.begin(), v.end(), i) == v.end())
            rem.push_back(i);
    }

    mt19937 mt(5);

    int ans = 1;
    while(!rem.empty()){
        if(rem.size() < k)
            return ans;

        v.clear();
        shuffle(rem.begin(), rem.end(), mt);
        move_inside(rem[0]);
        v.push_back(rem[0]);
        for(int i = 1; i < rem.size(); ++i){
            int x = rem[i];
            move_inside(x);
            if(press_button() == 1){
                v.push_back(x);
                if(v.size() == k)
                    break;
            }
            else{
                move_outside(x);
            }
        }
        for(int x: v)
            move_outside(x);
        if(v.size() < k)
            return ans;

        ++ans;
        vector<int> rem2;
        set<int> s;
        for(int x: v)
            s.insert(x);
        for(int x: rem)
            if(!s.count(x))
                rem2.push_back(x);
        swap(rem, rem2);
    }

    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:76:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |         if(rem.size() < k)
      |            ~~~~~~~~~~~^~~
insects.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 1; i < rem.size(); ++i){
      |                        ~~^~~~~~~~~~~~
insects.cpp:88:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |                 if(v.size() == k)
      |                    ~~~~~~~~~^~~~
insects.cpp:97:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |         if(v.size() < k)
      |            ~~~~~~~~~^~~

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