Submission #1217344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217344		user736482	Rarest Insects (IOI22_insects)	C++20	99.80 / 100	15 ms	488 KiB

insects

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000002022
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
bool czy[2007];
ll n;
void upd(ll a){
    if(czy[a])move_outside(a);
    else move_inside(a);
    czy[a]^=1;
}
ll gt(){return press_button();}
vector<ll>al;
void sh(){
    for(ll i=al.size()-1;i>=0;i--){
      //  swap(al[i],al[rand()%(i+1)]);
    }
}
int min_cardinality(int NN){
    al.clear();
    for(ll i=0;i<NN;i++)czy[i]=0;
    srand(15);
    n=NN;
    ll d=1;
    
    for(ll i=0;i<n;i++)al.pb(i);
    sh();
    upd(al[0]);
    vector<ll>v={al[0]},vpom;
    for(ll i=1;i<n;i++){
        upd(al[i]);
        if(gt()==2){upd(al[i]);vpom.pb(al[i]);}
        else {d++;v.pb(al[i]);}
    }
    if(d==1)return n;
    al=vpom;
    ll pocz=1;
    ll kon=n/d;
    while(pocz!=kon){
        //cout<<kon<<" ";
        ll mid=(pocz+kon+1+(1))/2;
        sh();
        ll ak=mid-pocz+d*pocz;
        vector<ll>v1,v2,v3;
        for(ll i=0;i<mid-pocz;i++){upd(al[i]);v2.pb(al[i]);}
        for(ll i=mid-pocz;i<al.size();i++){
            if(ak==mid*d){
                v1.pb(al[i]);
                continue;
            }
            if(ak+al.size()-i<mid*d){
              v3.pb(al[i]);
              continue;
            }
            upd(al[i]);
            if(gt()==mid+1){upd(al[i]);v1.pb(al[i]);}
            else {ak++;v2.pb(al[i]);}
        }
        if(ak==mid*d){
            al=v1;
            pocz=mid;
        }
        else{
            al=v2;
            for(ll i : v3)al.pb(i);
            kon=mid-1;
            for(ll i : v2)upd(i);
        }

        kon=min(kon,(ll)pocz+(ll)al.size()/d);
    }
    return pocz;
}

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