Submission #1175074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175074		onlk97	Rarest Insects (IOI22_insects)	C++17	57.95 / 100	40 ms	444 KiB

insects

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

int min_cardinality(int N){
    vector <int> f;
    int w[N],t[N];
    for (int i=0; i<N; i++){
        w[i]=-1;
        t[i]=0;
    }
    f.push_back(0); w[0]=0;
    move_inside(0);
    for (int i=1; i<N; i++){
        move_inside(i);
        if (press_button()==1){
            w[i]=f.size();
            f.push_back(i);
        } else move_outside(i); 
    }
    for (int i:f) move_outside(i);
    int m=f.size();
    for (int b=0; b<11; b++){
        vector <int> nd;
        for (int i=0; i<m; i++) if (i&(1<<b)) nd.push_back(i);
        if (nd.empty()) continue;
        vector <int> ins;
        for (int i=nd[0]; i<N; i++){
            if (w[i]!=-1){
                if (w[i]&(1<<b)){
                    move_inside(i);
                    ins.push_back(i);
                }
                continue;
            }
            move_inside(i);
            if (press_button()==2) t[i]+=(1<<b);
            move_outside(i);
        }
        for (int i:ins) move_outside(i);
    }
    map <int,int> mp;
    for (int i=0; i<N; i++){
        if (w[i]==-1) mp[t[i]]++;
        else mp[w[i]]++;
    }
    int ans=N;
    for (auto i:mp) ans=min(ans,i.second);
    return ans;
}

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