제출 #831293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831293		definitelynotmee	드문 곤충 (IOI22_insects)	C++17	70.87 / 100	111 ms	560 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)){
        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));
    }
    

    

}

컴파일 시 표준 에러 (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: 45.87 / 75