Submission #1075446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075446		Zicrus	Rarest Insects (IOI22_insects)	C++17	0 / 100	3075 ms	392 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) {
            if (cnt > 16) {
                int i = mt()%n;
                while (!remove(i)) i = mt()%n;
                int j = mt()%n;
                while (!remove(j)) j = mt()%n;
                int i1 = mt()%n;
                while (!remove(i)) i = mt()%n;
                int j1 = mt()%n;
                while (!remove(j)) j = mt()%n;
                cur = press_button();
                if (cur == mx) {
                    s.insert(i);
                    s.insert(j);
                    s.insert(i1);
                    s.insert(j1);
                }
                else {
                    add(j1);
                    add(i1);
                    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;
                    }
                }
            }
            else {
                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:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < s0.size(); i++) {
      |                         ~~^~~~~~~~~~~
insects.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             if (i == s0.size()-1) {
      |                 ~~^~~~~~~~~~~~~~

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