oj.uz

Submission #1085469

# Submission time Handle Problem Language Result Execution time Memory
1085469 2024-09-08T09:57:38 Z SamueleVid Rarest Insects (IOI22_insects) C++17
0 / 100
 98 ms 9008 KB 
#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(trg);
        if (x >= trg) types_dx.push_back(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 98 ms 9008 KB Too many queries.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 98 ms 9008 KB Too many queries.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 7512 KB Too many queries.
2 Halted 0 ms 0 KB -