Submission #628146

#	Time	Username	Problem	Language	Result	Execution time	Memory
628146		qwerasdfzxcl	Rarest Insects (IOI22_insects)	C++17	100 / 100	63 ms	552 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
mt19937 rng(1557);
vector<int> P;
set<int> qst, cd;
int n, t;

bool ins(int x){
    bool ret = qst.insert(x).second;
    if (ret) move_inside(P[x-1]);
    return ret;
}

bool del(int x){
    if (qst.find(x)==qst.end()) return 0;
    qst.erase(x);
    move_outside(P[x-1]);
    return 1;
}

void get_type(){
    for (int i=1;i<=n;i++){
        ins(i);
        if (press_button()>1) del(i);
    }

    t = qst.size();
    for (int i=1;i<=n;i++) if (qst.find(i)==qst.end()) cd.insert(i);
}

bool ok(int c){
    if (cd.empty()){
        return (int)qst.size() == t*c;
    }

    if (qst.find(*cd.begin())!=qst.end()){
        for (auto &x:cd) del(x);
    }

    for (auto &x:cd){
        ins(x);
        if (press_button()>c) del(x);
        if ((int)qst.size() == t*c) break;
    }

    bool ret = (int)qst.size() == t*c;
    for (auto iter=cd.begin();iter!=cd.end();){
        if ((qst.find(*iter)!=qst.end())==ret) iter = cd.erase(iter);
        else iter++;
    }

    return ret;
}

int min_cardinality(int N) {
    for (int i=0;i<N;i++) P.push_back(i);
    shuffle(P.begin(), P.end(), rng);
    n = N;
    get_type();
    if (t==1) return n;

    int l = 2, r = N / t, ans = 1;
    while(l<=r){
        int m = (l+r)>>1;
        if (ok(m)) l = m+1, ans = m;
        else r = m-1;
    }
    return ans;
}

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