oj.uz

Submission #1075446

# Submission time Handle Problem Language Result Execution time Memory
1075446 2024-08-26T06:22:17 Z Zicrus Rarest Insects (IOI22_insects) C++17
0 / 100
 2000 ms 392 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 392 KB Output is correct
6 Execution timed out 3075 ms 344 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 392 KB Output is correct
6 Execution timed out 3075 ms 344 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Execution timed out 3057 ms 344 KB Time limit exceeded
8 Halted 0 ms 0 KB -