Submission #766903

#	Time	Username	Problem	Language	Result	Execution time	Memory
766903		birktj	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	59 ms	336 KiB

insects

#include "insects.h"
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

stack<int> box, pile, discard;

void fill_box(int x) {
    while (!pile.empty()) {
        int i = pile.top();
        pile.pop();
        move_inside(i);
        box.push(i);
        int maxCount = press_button();
        if (maxCount > x) {
            move_outside(i);
            box.pop();
            discard.push(i);
        }
    }
}

void empty_box() {
    while (!box.empty()) {
        int i = box.top();
        box.pop();
        move_outside(i);
        discard.push(i);
    }
}

int min_cardinality(int N) {
    for (int i = 0; i < N; i++) {
        pile.push(i);
    }
    fill_box(1);
    swap(discard, pile);
    int k = box.size();
    empty_box();
    discard = {};

    //printCounts();

    //cerr << "piles size = " << pile.size() << endl; 
    //cerr << "discard size = " << discard.size() << endl; 
    //cerr << "box size = " << box.size() << endl; 

    int l = 1;
    int u = N/k;

    while (l + 1 <= u) {
        int m = (l + u + 1) / 2;

        //cerr << "m = " << m << endl;
        //cerr << "l = " << l << endl;

        fill_box(m - l);
        swap(discard, pile);
        empty_box();
        //cerr << "piles size = " << pile.size() << endl; 
        //cerr << "discard size = " << discard.size() << endl; 
        //cerr << "discard size + extra = " << discard.size() + k*l << endl; 

        //printCounts();

        if (discard.size() + k*l == m*k) {
            discard = {};
            l = m;
        } else {
            pile = {};
            swap(discard, pile);
            u = m-1;
        }
    }

    return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:68:34: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if (discard.size() + k*l == m*k) {
      |             ~~~~~~~~~~~~~~~~~~~~~^~~~~~

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