Submission #637129

#	Time	Username	Problem	Language	Result	Execution time	Memory
637129		someone	Rarest Insects (IOI22_insects)	C++17	99.58 / 100	63 ms	424 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
 
deque<int> act, nex, in;
 
int getMin(int nbType) {
    int n = act.size();
    if(nbType == 1)
        return n;
    if(nbType > n)
        return 0;
 
    int del = (int)ceil(0.5 * (double)n / (double)nbType);
    for(int i = 0; i < n; i++) {
        move_inside(act[i]);
        if(press_button() == del+1) {
            move_outside(act[i]);
            nex.push_back(act[i]);
        } else {
            in.push_back(act[i]);
        }
    }
    if((int)in.size() == del * nbType) {
        swap(act, nex);
        for(int i : in)
            move_outside(i);
        in.clear();
        nex.clear();
        return del + getMin(nbType);
    }
    for(int i : in)
        move_outside(i);
 
    deque<int> repr, garde;
    for(int i : nex) {
        move_inside(i);
        if(press_button() == 1) {
            repr.push_back(i);
        } else {
            move_outside(i);
        }
    }
    for(int i : in) {
        move_inside(i);
        if(press_button() == 1) {
            garde.push_back(i);
        }
        move_outside(i);
    }
    for(int i : repr)
        move_outside(i);
 
    swap(garde, act);
 
    garde.clear();
    nex.clear();
    in.clear();
    return getMin(nbType - (int)repr.size());
}
 
int min_cardinality(int N) {
    int nbType = 0;
    for(int i = 0; i < N; i++)
        act.push_back(i);
 
    for(int i = 0; i < N; i++) {
        move_inside(i);
        if(press_button() == 2) {
            move_outside(i);
            nex.push_back(i);
        } else {
            nbType++;
            in.push_back(i);
        }
    }
 
    for(int i : in)
        move_outside(i);
    swap(act, nex);
    nex.clear();
    in.clear();
 
    return getMin(nbType) + 1;
}

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