Submission #975010

#	Time	Username	Problem	Language	Result	Execution time	Memory
975010		pirhosig	Rarest Insects (IOI22_insects)	C++17	100 / 100	35 ms	1628 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
    
    
    
int min_cardinality(int N) {
    unordered_set<int> rem;
    
    for (int i = 0; i < N; ++i) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
            rem.insert(i);
        }
    }
    int T = N - rem.size();
    
    int low = 1;
    int upp = N / T;
    while (low < upp) {
        int mid = (low + upp + 1) / 2;
        vector<int> curr;
        int cnt = 0;
        for (int a : rem) {
            cnt++;
            move_inside(a);
            if (press_button() > mid) move_outside(a);
            else curr.push_back(a);

            if (curr.size() == (mid - low) * T) break;
        }
    
        if (curr.size() == (mid - low) * T) {
            low = mid;
            for (int a : curr) rem.erase(a);
        }
        else {
            upp = mid - 1;
            rem.clear();
            for (int a : curr) {
                move_outside(a);
                rem.insert(a);
            }
        }
    }
    
    return low;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:31:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |             if (curr.size() == (mid - low) * T) break;
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
insects.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if (curr.size() == (mid - low) * T) {
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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