제출 #1240656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240656		someone	드문 곤충 (IOI22_insects)	C++17	95.37 / 100	20 ms	416 KiB

insects

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

int nbInside = 0;
vector<bool> in, alive;

void inside(int i) {
    if(in[i]) return;
    in[i] = true;
    move_inside(i);
    nbInside++;
}

void outside(int i) {
    if(!in[i]) return;
    in[i] = false;
    move_outside(i);
    nbInside--;
}

int getNbType(int N) {
    int nb = 0;
    for(int i = 0; i < N; i++)
        if(alive[i]) {
            nb++;
            inside(i);
            if(press_button() == 2) {
                nb--;
                outside(i);
            }
        }
    for(int i = 0; i < N; i++)
        outside(i);
    return nb;
}

int min_cardinality(int n) {
    in.resize(n);
    alive.resize(n);
    int nbAlive = n;
    for(int i = 0; i < n; i++) alive[i] = true;

    int nbType = getNbType(n),
        majorant = 1000*1000, suppr = 0;

    while(majorant * nbType > nbAlive) {
        int test = (int)ceil((0.5 * nbAlive) / nbType);
        for(int i = 0; i < n; i++)
            if(alive[i]) {
                inside(i);
                if(press_button() > test)
                    outside(i);
            }
        if(nbInside == nbType * test) {
            suppr += test;
            majorant -= test;
            for(int i = 0; i < n; i++)
                if(in[i]) {
                    alive[i] = false;
                    nbAlive--;
                }
            for(int i = 0; i < n; i++)
                outside(i);
            if(nbType > getNbType(n))
                majorant = 0;
        } else {
            majorant = test;
            for(int i = 0; i < n; i++)
                if(!in[i] && alive[i]) {
                    alive[i] = false;
                    nbAlive--;
                }
            for(int i = 0; i < n; i++)
                outside(i);
        }
    }

    if(nbAlive == 0) majorant = 0;
    return majorant + suppr;
}

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