Submission #736846

#	Time	Username	Problem	Language	Result	Execution time	Memory
736846		onlk97	Rarest Insects (IOI22_insects)	C++17	10 / 100	165 ms	208 KiB

insects

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

const int thres=20;
int min_cardinality(int N) {
    mt19937 mt(time(nullptr));
    vector <int> v;
    for (int i=0; i<N; i++) v.push_back(i);
    shuffle(v.begin(),v.end(),mt);
    int belong[N];
    for (int i=0; i<N; i++) belong[i]=-1;
    belong[v[0]]=0;
    int curidx=0;
    bool dead[N];
    for (int i=0; i<N; i++) dead[i]=0;
    map <int,pair <int,int> > alive;
    alive[0]={1,v[0]};
    for (int i=0; i<N; i++){
        move_inside(v[i]);
        if (i){
            int t=press_button();
            if (t==1){
                curidx++;
                belong[v[i]]=curidx;
                while (alive.size()>=thres){
                    vector <int> candidates;
                    int mx=-1;
                    for (auto i:alive){
                        if (i.second.first>mx){
                            candidates.clear();
                            mx=i.second.first;
                        }
                        if (i.second.first==mx){
                            candidates.push_back(i.first);
                        }
                    }
                    shuffle(candidates.begin(),candidates.end(),mt);
                    dead[candidates.front()]=1;
                    alive.erase(candidates.front());
                }
                alive[curidx]={1,v[i]};
            } else {
                vector <int> candidates,addback;
                for (auto j:alive) candidates.push_back(j.second.second);
                while (candidates.size()>1){
                    int mid=candidates.size()/2;
                    for (int j=0; j<mid; j++) move_outside(candidates[j]);
                    int tp=press_button();
                    if (tp==2){
                        for (int j=0; j<mid; j++) addback.push_back(candidates[j]);
                        candidates.erase(candidates.begin(),candidates.begin()+mid);
                    } else {
                        for (int j=0; j<mid; j++) move_inside(candidates[j]);
                        while (candidates.size()>mid) candidates.pop_back();
                    }
                }
                int tp2=press_button();
                if (tp2==2){
                    belong[v[i]]=belong[candidates[0]];
                    alive[belong[v[i]]].first++;
                }
                for (int j:addback) move_inside(j);
                move_outside(v[i]);
            }
        }
    }
    int ans=N;
    for (auto i:alive) ans=min(ans,i.second.first);
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:55:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |                         while (candidates.size()>mid) candidates.pop_back();
      |                                ~~~~~~~~~~~~~~~~~^~~~
insects.cpp:15:10: warning: variable 'dead' set but not used [-Wunused-but-set-variable]
   15 |     bool dead[N];
      |          ^~~~

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