Submission #831295

#	Time	Username	Problem	Language	Result	Execution time	Memory
831295		definitelynotmee	Rarest Insects (IOI22_insects)	C++17	86.78 / 100	98 ms	580 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>>;

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() > sqrt(N)*0.25){
        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)*0.3+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 {
        vector<int> resp(resto.size());

        int logg = log2(dif.size());

        for(int k = 0; k <= logg; k++){
            for(int i = 0; i < dif.size(); i++){
                if((1<<k)&i){
                    if(!m.s.count(dif[i]))
                        m.insert(dif[i]);
                } else {
                    if(m.s.count(dif[i]))
                        m.erase(dif[i]);
                }
            }

            for(int i = 0; i < resto.size(); i++){
                m.insert(resto[i]);
                if(m.resp() == 2)
                    resp[i] |= 1<<k;
                m.erase(resto[i]);
            }
        }

        vector<int> ct(dif.size(), 1);

        for(int i : resp)
            ct[i]++;
        
        return *min_element(all(ct));
    }
    

    

}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:101:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for(int i = 0; i < dif.size(); i++){
      |                            ~~^~~~~~~~~~~~
insects.cpp:111:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for(int i = 0; i < resto.size(); i++){
      |                            ~~^~~~~~~~~~~~~~

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