Submission #1085492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085492		SamueleVid	Rarest Insects (IOI22_insects)	C++17	61.79 / 100	103 ms	980 KiB

insects

#include <bits/stdc++.h>
using namespace std;
 
void move_inside(int i);
void move_outside(int i);
int press_button();
 
set<int> dentro;

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 (usable.size() == 0) {
        for (auto x : types) res.push_back(1);
        return 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;

    // praticamente ne tolgo solo alcuni perché potrebbero essere già alcuni giusti
    set<int> types_dx_set;
    for (auto x : types_dx) types_dx_set.insert(x);
    vector<int> to_remove, to_add;
    
    for (auto x : dentro) {
        if (!types_dx_set.count(x)) {
            to_remove.push_back(x);
            move_outside(x);
        }
    }
    for (auto x : to_remove) dentro.erase(x);

    for (auto x : types_dx_set) {
        if (!dentro.count(x)) {
            to_add.push_back(x);
            move_inside(x);
        }
    }
    for (auto x : to_add) dentro.insert(x);
    // ora dentro ci sono solo quelli di types_dx
    
    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_dx = sol(types_dx, pusha_dx); // vado prima a destra per conservare alcuni in dentro
    vector<int> res_sx = sol(types_sx, pusha_sx);
    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) dentro.insert(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:20:19: warning: unused variable 'x' [-Wunused-variable]
   20 |         for (auto x : types) res.push_back(1);
      |                   ^
insects.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < types.size() / 2; i ++) types_sx.push_back(types[i]);
      |                     ~~^~~~~~~~~~~~~~~~~~
insects.cpp:36:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     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: 36.79 / 75