Submission #1113732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113732		db_123	Rarest Insects (IOI22_insects)	C++17	98.92 / 100	122 ms	844 KiB

insects

#include "insects.h"
#include <vector>
#include <set>
#include <unordered_map> 
 
using namespace std;
 
int n;
 
void check(int N, int d, int &always_add, int &rsBs, vector<bool> &vis) {
 
    int mid = N / (2 * d);
    if(mid == 0)
        mid = 1;
 
    vector<int> poz;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            continue;
        }
        move_inside(i - 1);
        if (press_button() > mid) {
            move_outside(i - 1);
            continue;
        }
        poz.emplace_back(i);
    }
 
    for (auto it : poz) {
        move_outside(it - 1);
    }
 
    if (poz.size() == mid * d) { /// e plin
        for (auto it : poz) {
            vis[it] = true;
        }
        always_add += poz.size() / d;
    }
    else if (poz.size() < mid * d) { /// nu e plin
        rsBs = min(rsBs, mid);
 
        int idx = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            while (idx < poz.size() && poz[idx] < i) {
                idx ++;
            }
            if (poz[idx] != i) {
                vis[i] = true;
            }
        }
    }
    return;
}
 
int min_cardinality(int N) {
 
    vector<bool> vis(N + 1);
	n = N;
 
    int d = 0;
    {
        vector<int> temp;
        for (int i = 1; i <= n; i++) {
            move_inside(i - 1);
            if (press_button() > 1) {
                move_outside(i - 1);
                continue;
            }
            temp.emplace_back(i);
        }
        d = temp.size();
        for (auto it : temp) {
            move_outside(it - 1);
        }
    }
 
    int always_add = 0, rsBs = 1e9;
    while (N >= d) {
        check(N, d, always_add, rsBs, vis);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            cnt ++;
        }
        N = cnt;
    }
 
    return always_add;
}

Compilation message (stderr)

insects.cpp: In function 'void check(int, int, int&, int&, std::vector<bool>&)':
insects.cpp:33:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     if (poz.size() == mid * d) { /// e plin
      |         ~~~~~~~~~~~^~~~~~~~~~
insects.cpp:39:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     else if (poz.size() < mid * d) { /// nu e plin
      |              ~~~~~~~~~~~^~~~~~~~~
insects.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             while (idx < poz.size() && poz[idx] < i) {
      |                    ~~~~^~~~~~~~~~~~

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