Submission #728528

#	Time	Username	Problem	Language	Result	Execution time	Memory
728528		grogu	Rarest Insects (IOI22_insects)	C++17	0 / 100	5 ms	324 KiB

insects

#include "insects.h"
#define dbg(x) cerr<<#x<<": "<<x<<endl
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>

using namespace std;
#define maxn 2005
ll n;
set<ll> s;
ll uniq = 0;
ll a[maxn];
ll F[maxn];
bool ok[maxn];
ll val[maxn];
ll cur = 0;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void add(ll i){
    if(s.find(i)!=s.end()) return;
    move_inside(a[i]);
    s.insert(i);
}
void del(ll i){
    if(s.find(i)==s.end()){
        cerr<<"out"<<endl;
        return;
    }
    move_outside(a[i]);
    s.erase(i);
}
ll get(){return press_button();}
void klir(){
    while(s.size()) del(*s.begin());
}
ll f(ll x){
    if(F[x]!=-1) return F[x];
    if(cur>x){
        for(ll i = n-1;i>=0;i--){
            if(s.find(i)!=s.end()&&val[i]>x) del(i);
        }
    }
    for(ll i = 0;i<n;i++){
        add(i);
        cur = get();
        if(cur>x) del(i);
        else val[i] = cur;
    }
    return F[x] = s.size();
}
ll min_cardinality(ll N) {
    for(ll i = 0;i<maxn;i++) F[i] = -1;
    n = N;
    for(ll i = 0;i<n;i++) a[i] = i;
    shuffle(a,a+n,rng);
    uniq = f(1);
    dbg(uniq);
    for(ll rez = 2;rez<=n;rez++){
        for(ll i = 0;i<n;i++){
            if(ok[i]){
                add(i);
                ok[i] = 0;
            }else{
                add(i);
                cur = get();
                if(cur>rez) ok[i] = 1,del(i);
            }
        }
        if(s.size()!=rez*uniq) return rez-1;
    }
    return n;
}
/**
6
5 8 9 5 9 9
**/

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:68:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if(s.size()!=rez*uniq) return rez-1;
      |            ~~~~~~~~^~~~~~~~~~

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