Submission #824315

#	Time	Username	Problem	Language	Result	Execution time	Memory
824315		vjudge1	Rarest Insects (IOI22_insects)	C++17	89.82 / 100	90 ms	440 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
random_device seed;
mt19937 rng(seed());
vector <int> rest;
void check(int x, int dist) {
    move_inside(x);
    if (press_button() != dist) {
        rest.push_back(x);
        move_outside(x);
    }
}
int min_cardinality(int N) {
    rest.clear();
    for (int i = 0; i < N; i++)
        check(i, 1);
    int ans = 1, cnt = N - rest.size();
    while(rest.size()) {
        vector<int> rest2 = rest;
        rest.clear();
        shuffle(rest2.begin(), rest2.end(), rng);
        for(int i = 0; i < rest2.size(); i++) {
            if(i<rest.size()+cnt)
                check(rest2[i], ans+1);
            else
                rest.push_back(rest2[i]);
        }
        if (rest2.size() < rest.size() +cnt)
            return ans;
        ans++;
    }
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i = 0; i < rest2.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~
insects.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             if(i<rest.size()+cnt)
      |                ~^~~~~~~~~~~~~~~~

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