Submission #1085472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085472		SamueleVid	Rarest Insects (IOI22_insects)	C++17	54.87 / 100	112 ms	1232 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, int l, int r) {
    // 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() == 0) {
        return {};
    }
    if (types.size() == 1) {
        res.push_back(usable.size() + 1);
        return res;
    }
    vector<int> sx, dx;


    int trg = (l + r) / 2;
    
    for (auto i : usable) {
        if (i < trg) sx.push_back(i);
        else dx.push_back(i);
    }

    vector<int> types_sx, types_dx;
    for (auto x : types) {
        if (x < trg) types_sx.push_back(x);
        if (x >= trg) types_dx.push_back(x);
    }

    if (types_sx.empty()) {
        return sol(types, usable, trg, r);
    }
    if (types_dx.empty()) {
        return sol(types, usable, l, trg);
    }

    // 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, l, trg);
    vector<int> res_dx = sol(types_dx, pusha_dx, trg, r);
    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, 0, N);

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

    return minim;
}

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