Submission #1075188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075188		Zicrus	Rarest Insects (IOI22_insects)	C++17	68.05 / 100	93 ms	952 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
 
typedef long long ll;
 
int n;
vector<bool> in;
unordered_set<int> s;
int cnt;
 
int add(int i) {
    if (in[i]) return 0;
    move_inside(i);
    cnt++;
    in[i] = true;
    return 1;
}
 
int remove(int i) {
    if (!in[i]) return 0;
    move_outside(i);
    cnt--;
    in[i] = false;
    return 1;
}
 
int min_cardinality(int N) {
    n = N;
    cnt = 0;
    mt19937 mt(time(0));
    in = vector<bool>(n);
    for (int i = 0; i < n; i++) {
        add(i);
    }
    int mx = press_button();
    int prevSz = cnt;
    while (mx > 1) {
        int cur = mx;
        while (cur == mx) {
            int i = mt()%n;
            while (!remove(i)) i = mt()%n;
            int j = mt()%n;
            while (!remove(j)) j = mt()%n;
            cur = press_button();
            if (cur == mx) {
                s.insert(i);
                s.insert(j);
            }
            else {
                add(j);
                cur = press_button();
                if (cur == mx) {
                    s.insert(i);
                    remove(j);
                }
                cur = mx-1;
            }
        }
        vector<int> s0;
        for (auto &e : s) {
            s0.push_back(e);
        }
        shuffle(s0.begin(), s0.end(), mt);
        for (int i = 0; i < s0.size(); i++) {
            if (i == s0.size()-1) {
                if (add(s0[i])) {
                    cur = press_button();
                    if (cur == mx) remove(s0[i]);
                }
                continue;
            }

            add(s0[i]);
            add(s0[i+1]);
            cur = press_button();
            if (cur == mx) {
                remove(s0[i+1]);
                cur = press_button();
                if (cur == mx) {
                    remove(s0[i]);
                }
                else {
                    i++;
                }
            }
        }
        if (cnt * mx % (mx-1) == 0 && cnt * mx / (mx-1) == prevSz) {
            break;
        }
        s.clear();
        prevSz = cnt;
        mx--;
    }
    return mx;
} 
 
#ifdef TEST
#include "grader.cpp"
#endif

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < s0.size(); i++) {
      |                         ~~^~~~~~~~~~~
insects.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (i == s0.size()-1) {
      |                 ~~^~~~~~~~~~~~~~

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