Submission #831317

#	Time	Username	Problem	Language	Result	Execution time	Memory
831317		definitelynotmee	Rarest Insects (IOI22_insects)	C++17	87.89 / 100	84 ms	592 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using ll = long long;
using namespace std;
template<typename T>
using matrix = vector<vector<T>>;

const double coef_bin_search = 0.4, coef_sqrt = 0.13;

struct Machine {
    set<int> s;

    void insert(int id){
        s.insert(id);
        move_inside(id);
    }
    void erase(int id){
        s.erase(id);
        move_outside(id);
    }

    int resp(){
        return press_button();
    }
    void clear(){
        auto it  = s.begin();
        while(it!=s.end()){
            move_outside(*it);
            it = s.erase(it);
        }
    }
};

int min_cardinality(int N) {
    mt19937 rng(time(nullptr));
    vector<int> dif;
    vector<int> resto;

    Machine m;

    for(int i = 0; i < N; i++){
        m.insert(i);
        if(m.resp() == 1){
            dif.push_back(i);
        } else m.erase(i), resto.push_back(i);
    }

    shuffle(all(dif),rng);
    shuffle(all(resto),rng);


    m.clear();

    if(dif.size() > N*coef_sqrt/dif.size()){
        int ini = 1, fim = N/dif.size();


        auto putless =[&](int mx){
            for(int i : resto){
                if(m.s.count(i))
                    continue;
                m.insert(i);
                if(m.resp() > mx)
                    m.erase(i);
            }
        };

        int last = -1;

        while(ini!=fim){
            int mid = (fim-ini)*coef_bin_search+ini;
            while(mid <= ini)
                mid++;

            // cerr << "mid = " << mid << '\n';
            
            if(mid < last)
                m.clear();
            
            putless(mid-1);

            bool ok = 1;

            for(int i : dif){
                m.insert(i);
                ok&= m.resp() == mid;
                m.erase(i);
            }

            if(ok)
                ini = mid;
            else fim = mid-1;
            last = mid;
        } 
        return ini;
    } else {
        int resp = N;

        auto dq =[&](vector<int> dif, vector<int> resto, bool flag, auto dq) -> void {
            if(dif.size() == 1 || resto.size() == 0){
                resp = min(resp,(int)resto.size());
                return;
            }
            
            int mid = dif.size()/2;

            if(flag){
                for(int i = mid; i < dif.size(); i++)
                    m.erase(dif[i]);
            } else{
                for(int i = 0; i < mid; i++){
                    m.insert(dif[i]);
                }
            }

            vector<int> ldif, rdif, lresto, rresto;

            for(int i = 0; i < mid; i++)
                ldif.push_back(dif[i]);
            
            for(int i = mid; i < dif.size(); i++)
                rdif.push_back(dif[i]);
            
            for(int i : resto){
                m.insert(i);
                if(m.resp() == 2)
                    lresto.push_back(i);
                else rresto.push_back(i);
                m.erase(i);
            }

            dq(ldif,lresto,1,dq);
            m.clear();
            dq(rdif,rresto,0,dq);
        };

        
        dq(dif,resto,0,dq);
        return resp+1;
    }
    

    

}

Compilation message (stderr)

insects.cpp: In lambda function:
insects.cpp:109:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 for(int i = mid; i < dif.size(); i++)
      |                                  ~~^~~~~~~~~~~~
insects.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int i = mid; i < dif.size(); i++)
      |                              ~~^~~~~~~~~~~~
insects.cpp: In instantiation of 'min_cardinality(int)::<lambda(std::vector<int>, std::vector<int>, bool, auto:23)> [with auto:23 = min_cardinality(int)::<lambda(std::vector<int>, std::vector<int>, bool, auto:23)>]':
insects.cpp:139:26:   required from here
insects.cpp:109:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 for(int i = mid; i < dif.size(); i++)
      |                                  ~~^~~~~~~~~~~~
insects.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int i = mid; i < dif.size(); i++)
      |                              ~~^~~~~~~~~~~~

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