Submission #628629

#	Time	Username	Problem	Language	Result	Execution time	Memory
628629		Sorting	Rarest Insects (IOI22_insects)	C++17	90.81 / 100	138 ms	340 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 get_ans(vector<int> rem, int k){
    mt19937 mt(6);
    vector<int> v;

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

        v.clear();
        shuffle(rem.begin(), rem.end(), mt);
        for(int i = 0; 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;
}

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);
    }
    
    if(k >= 20)
        return get_ans(rem, k);

    vector<bool> in_v(n, false);
    for(int x: v)
        in_v[x] = true;

    for(int i = 0; i < 1; ++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> rem2[2];
    for(int i = 0; i < n; ++i){
        if(in_v[i]) continue;
        rem2[type[i]].push_back(i);
    }
    return min(get_ans(rem2[0], (k + 1) / 2), get_ans(rem2[1], k / 2));
}

Compilation message (stderr)

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

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