Submission #1085463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085463		SamueleVid	Rarest Insects (IOI22_insects)	C++17	58.35 / 100	113 ms	1104 KiB

insects

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

void move_inside(int i);
void move_outside(int i);
int press_button();

vector<int> sol(vector<int> types, vector<int> usable) {
    // cout << "types : ";
    // for (auto x : types) cout << x << " ";
    // cout << '\n';
    // cout << "usable : ";
    // for (auto x : usable) cout << x << " ";
    // cout << '\n';

    vector<int> res;
    if (types.size() == 1) {
        res.push_back(usable.size() + 1);
        return res;
    }
    vector<int> sx, dx;
    
    for (auto i : usable) {
        if (i < types[types.size() / 2]) sx.push_back(i);
        else dx.push_back(i);
    }

    vector<int> types_sx, types_dx;
    for (int i = 0; i < types.size() / 2; i ++) types_sx.push_back(types[i]);
    for (int i = types.size() / 2; i < types.size(); i ++) types_dx.push_back(types[i]);

    // cout << "mezzo : " << types[types.size() / 2] << '\n';
    // cout << "dx : ";
    // for (auto x : dx) cout << x << " ";
    // cout << '\n'; 
    // cout << "type_dx : ";
    // for (auto x : types_dx) cout << x << " ";
    // cout << '\n'; 

    vector<int> pusha_sx = sx;
    vector<int> pusha_dx;
    for (auto x : types_dx) move_inside(x);
    for (auto x : dx) {
        move_inside(x);
        if (press_button() == 2) { // fa parte dei gruppi
            pusha_dx.push_back(x);
        }
        else { // == 1, è dei gruppi a sinistra
            pusha_sx.push_back(x);
        }
        move_outside(x);
    }
    for (auto x : types_dx) move_outside(x);

    vector<int> res_sx = sol(types_sx, pusha_sx);
    vector<int> res_dx = sol(types_dx, pusha_dx);
    for (auto x : res_sx) res.push_back(x);
    for (auto x : res_dx) res.push_back(x);

    return res;
}

int min_cardinality(int N) {
    // il primo elemento di tutti i gruppi
    vector<int> types;
    for (int i = 0; i < N; i ++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
            continue;
        }
        types.push_back(i);
    }
    for (auto x : types) move_outside(x);

    set<int> types_set;
    for (auto x : types) types_set.insert(x);

    vector<int> usable;
    for (int i = 0; i < N; i ++) if (!types_set.count(i)) usable.push_back(i);
    vector<int> res = sol(types, usable);

    int minim = N;
    for (auto x : res) minim = min(minim, x);

    return minim;
}

Compilation message (stderr)

insects.cpp: In function 'std::vector<int> sol(std::vector<int>, std::vector<int>)':
insects.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < types.size() / 2; i ++) types_sx.push_back(types[i]);
      |                     ~~^~~~~~~~~~~~~~~~~~
insects.cpp:30:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = types.size() / 2; i < types.size(); i ++) types_dx.push_back(types[i]);
      |                                    ~~^~~~~~~~~~~~~~

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