Submission #830514

#	Time	Username	Problem	Language	Result	Execution time	Memory
830514		tolbi	Rarest Insects (IOI22_insects)	C++17	10 / 100	307 ms	336 KiB

insects

    #include <bits/stdc++.h>
    using namespace std;
    mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
    #include "insects.h"
    int min_cardinality(int n) {
        vector<int> par(n);
        function<int(int)> find = [&](int node)->int{
            if (par[node]==node) return node;
            return par[node]=find(par[node]);
        };
        vector<int> hueh(n);
        iota(hueh.begin(), hueh.end(), 0);
        for (int i = n-1; i >= 0; i--){
            swap(hueh[i],hueh[ayahya()%(i+1)]);
        }
        vector<int> sz(n,1);
        iota(par.begin(), par.end(), 0);
        vector<int> crr;
        function<int()> findx;
        findx = [&]()->int{
            for (int i = 0; i < crr.size(); i++){
                move_outside(crr[i]);
                if (press_button()==1){
                    for (int j=0;j<=i;j++){
                        move_inside(crr[j]);
                    }
                    return i;
                }
            }
            return 23;
        };
        for (int kk = 0; kk < n; kk++){
            int i = hueh[kk];
            move_inside(i);
            if (press_button()>1){
                int pos = crr[findx()];
                sz[find(pos)]+=sz[find(i)];
                sz[find(i)]=0;
                par[i]=find(pos);
                move_outside(i);
            }
            else crr.push_back(i);
        }
        int ans = n;
        for (int i = 0; i < n; i++){
            if (find(i)!=i) continue;
            ans=min(ans,sz[i]);
        }
        return ans;
    }

Compilation message (stderr)

insects.cpp: In lambda function:
insects.cpp:21:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             for (int i = 0; i < crr.size(); i++){
      |                             ~~^~~~~~~~~~~~

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