Submission #627684

#	Time	Username	Problem	Language	Result	Execution time	Memory
627684		emuyumi	Rarest Insects (IOI22_insects)	C++17	25 / 100	3090 ms	428 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"

using namespace std;

int min_cardinality(int N){
    vector<int> out, in;
    int types = 0;
    for (int i = 0; i < N; ++i){
        move_inside(i);
        in.push_back(i);
        if (press_button() != 1){
            move_outside(i);
            in.pop_back();
            out.push_back(i);
        }
        else types++;
    }
    if (types == 1){
        return N;
    }

    for (int x : in){
        move_outside(x);
    }
    in.clear();

    int hi = (N - types) / types;
    int ans = 1;
    for (int b = __lg(hi); b >= 0; --b){
        vector<int> tmp = out;
        out.clear();
        for (int x : tmp){
            move_inside(x);
            in.push_back(x);
            if (press_button() > (1<<b)){
                move_outside(x);
                in.pop_back();
                out.push_back(x);
            }
        }
        if (in.size() == types * (1<<b)){
            ans += (1<<b);
            for (int x : in){
                move_outside(x);
            }
            in.clear();
        }
        else{
            int cnt = in.size();
            int need = types * (1<<b);
            hi = min(hi, cnt / types);
            b = min(b, __lg(hi)+1);
            out.clear();
            for (int x : in){
                move_outside(x);
            }
            swap(in, out);
        }
    }
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:42:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         if (in.size() == types * (1<<b)){
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~
insects.cpp:51:17: warning: unused variable 'need' [-Wunused-variable]
   51 |             int need = types * (1<<b);
      |                 ^~~~

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