Submission #1075459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075459		Zicrus	Rarest Insects (IOI22_insects)	C++17	61.07 / 100	83 ms	708 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 numA, numP;
 
int add(int i) {
    if (in[i]) return 0;
    move_inside(i);
    cnt++;
    in[i] = true;
    numA++;
    return 1;
}
 
int remove(int i) {
    if (!in[i]) return 0;
    move_outside(i);
    cnt--;
    in[i] = false;
    return 1;
}

int press() {
    numP++;
    return press_button();
}
 
int min_cardinality(int N) {
    n = N;
    cnt = 0;
    numA = numP = 0;
    mt19937 mt(time(0));
    in = vector<bool>(n);
    for (int i = 0; i < n; i++) {
        add(i);
    }
    int mx = press();
    int prevSz = cnt;
    while (mx > 1) {
        int cur = mx;
        while (cur == mx) {
            if (numP > numA) {
                int i = mt()%n;
                while (!remove(i)) i = mt()%n;
                int j = mt()%n;
                while (!remove(j)) j = mt()%n;
                cur = press();
                if (cur == mx) {
                    s.insert(i);
                    s.insert(j);
                }
                else {
                    add(j);
                    cur = press();
                    if (cur == mx) {
                        s.insert(i);
                        remove(j);
                    }
                    cur = mx-1;
                }
            }
            else {
                int i = mt()%n;
                while (!remove(i)) i = mt()%n;
                cur = press();
                if (cur == mx) {
                    s.insert(i);
                }
            }
        }
        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();
                    if (cur == mx) remove(s0[i]);
                }
                continue;
            }
 
            if (numP > numA) {
                add(s0[i]);
                add(s0[i+1]);
                cur = press();
                if (cur == mx) {
                    remove(s0[i+1]);
                    cur = press();
                    if (cur == mx) {
                        remove(s0[i]);
                    }
                    else {
                        i++;
                    }
                }
            }
            else {
                add(s0[i]);
                cur = press();
                if (cur == mx) {
                    remove(s0[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:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i = 0; i < s0.size(); i++) {
      |                         ~~^~~~~~~~~~~
insects.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             if (i == s0.size()-1) {
      |                 ~~^~~~~~~~~~~~~~

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