제출 #1335738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1335738		yhkhoo	Rarest Insects (IOI22_insects)	C++17	95.06 / 100	63 ms	464 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

#define qry() press_button()
#define vi basic_string<int>
#define cnt count(cur.begin(), cur.end(), 1)
vector<int> o;

void in(int x){
    move_inside(o[x]);
}

void out(int x){
    move_outside(o[x]);
}

int min_cardinality(int n) {
    mt19937 rnd(67);
    o.clear();
    o.resize(n);
    for(int i=0; i<n; i++){
        o[i] = i;
    }
    shuffle(o.begin(), o.end(), rnd);

    vi f, nf;
    for(int i=0; i<n; i++){
        in(i);
        if(qry() == 1){
            f += i;
        }
        else{
            out(i);
            nf += i;
        }
    }
    int l = 1, r = n / f.size(), m;
    vector<bool> cur(n), good(n), prev(n);
    bool down = 0;
    while(l < r){
        m = (l+r+1)/2;
        /*cerr << m << '\n';
        if(m){
            for(auto i: nf){
                if(cur[i]) cerr << i << ' ';
            }
        }
        cerr << '\n';*/
        for(auto i: nf){
            if(cnt == (m-1) * f.size()) break;
            if(down){
                if(prev[i] && (!good[i])){
                    in(i);
                    if(qry() > m){
                        out(i);
                        cur[i] = 0;
                    }
                    else{
                        cur[i] = 1;
                    }
                }
            }
            else{
                if(!good[i]){
                    in(i);
                    if(qry() > m){
                        out(i);
                        cur[i] = 0;
                    }
                    else{
                        cur[i] = 1;
                    }
                }
            }
        }
        prev = cur;
        if(cnt != (m-1) * f.size()){ // m too big
            r = m-1;
            down = 1;
            for(auto i: nf){
                if(cur[i] && (!good[i])){
                    out(i);
                    cur[i] = 0;
                }
            }
        }
        else{ // m ok
            l = m;
            down = 0;
            for(auto i: nf){
                if(cur[i]) good[i] = 1;
            }
        }
    }
    return l;
}

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