Submission #629053

#	Time	Username	Problem	Language	Result	Execution time	Memory
629053		jhhope1	Rarest Insects (IOI22_insects)	C++17	95.36 / 100	85 ms	556 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
typedef long long ll;
int g;
int f(int h, int H, vector<int> V){
    if(H == h) return h;
    vector<int> O, I;
    for(int x: V){
        move_inside(x);
        if(press_button() == (h + H + 1) / 2 + 1){
            move_outside(x);
            O.push_back(x);
        }
        else{
            I.push_back(x);
        }
    }
    if(((H + h + 1) / 2 - h) * g == I.size()){
        return f((h + H + 1)/2, H, O);
    }
    for(int x: I){
        move_outside(x);
    }
    return f(h, (h + H + 1)/2 - 1, I);
}

int min_cardinality(int N) {
    move_inside(0);
    vector<int> V;
    for(int i=0 ; i<N ; i++){
        move_inside(i);
        if(press_button() == 2){
            move_outside(i);
            V.push_back(i);
        }
    }
    g = N - V.size();
    vector<int> W;
    for(int x: V){
        move_inside(x);
        if(press_button() > N/g){
            move_outside(x);
        }
        else{
            W.push_back(x);
        }
    }
    for(int x: W){
        move_outside(x);
    }
    return f(1, N/g, W);
}

Compilation message (stderr)

insects.cpp: In function 'int f(int, int, std::vector<int>)':
insects.cpp:19:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if(((H + h + 1) / 2 - h) * g == I.size()){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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