oj.uz

Submission #627646

# Submission time Handle Problem Language Result Execution time Memory
627646 2022-08-12T17:58:58 Z Tigerpants Rarest Insects (IOI22_insects) C++17
0 / 100
 21 ms 208 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <random>

using namespace std;

typedef vector<int> vi;
typedef set<int> si;
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<bool> vb;

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
    vi x(N);
    for (int i = 0; i < N; i++) {
        x[i] = i;
    }
    
    auto rd = random_device {};
    auto rng = default_random_engine { rd() };
    shuffle(x.begin(), x.end(), rng);

    vb roots(N, false);
    vb inside(N, false);
    vb permanent(N, false);

    int no_roots = 1;
    roots[0] = true;
    move_inside(x[0]);
    inside[0] = true;
    permanent[0] = true;

    for (int i = 1; i < N; i++) {
        move_inside(x[i]);
        inside[i] = true;
        if (press_button() == 2) {
            move_outside(x[i]);
            inside[i] = false;
        } else {
            roots[i] = true;
            permanent[i] = true;
            no_roots++;
        }
    }

    vb active(N, true); // remove those which are too big
    
    if (no_roots == 1) {
        return N;
    }

    if (no_roots == 2) {
        // include root[0]
        // add next
        // press -> get which group
        // remove next
        int a = 1;
        int b = 1;
        for (int i = 1; i < N; i++) {
            if (roots[i]) {
                move_outside(x[i]);
            }
        }
        for (int i = 1; i < N; i++) {
            if (!roots[i]) {
                move_inside(x[i]);
                if (press_button() == 2) {
                    a++;
                } else {
                    b++;
                }
                move_outside(x[i]);
            }
        }
        return min<int>(a, b);
    }

    if (no_roots == 3) {
        int a = 1;
        int b = 1;
        int c = 1;
        int c_root;
        for (int i = 1; i < N; i++) {
            if (roots[i]) {
                move_outside(x[i]);
                c_root = i;
            }
        }
        for (int i = 1; i < N; i++) {
            if (!roots[i]) {
                move_inside(x[i]);
                if (press_button() == 2) {
                    a++;
                } else {
                    move_inside(x[c_root]);
                    if (press_button() == 2) {
                        c++;
                    } else {
                        b++;
                    }
                    move_outside(x[c_root]);
                }
                move_outside(x[i]);
            }
        }
        return min<int>(a, min<int>(b, c));
    }

    int no_inside = no_roots;
    
    int high = ((N + no_roots - 1) / no_roots);
    int low = 4;
    while (low + 1 < high) {
        int middle = (low + high) / 2;
        for (int i = 0; i < N; i++) {
            if ((!inside[i]) && (active[i])) {
                move_inside(x[i]);
                inside[i] = true;
                no_inside++;
                if (no_inside >= no_roots + middle) {
                    if (press_button() > middle) {
                        move_outside(x[i]);
                        inside[i] = false;
                        no_inside--;
                    }
                }
            }
        }
        if (no_inside == middle * no_roots) {
            low = middle;
            // don't remove them. make them permanent
            for (int i = 0; i < N; i++) {
                if (inside[i]) {
                    permanent[i] = true;
                }
            }
        } else {
            high = middle;
            // deactivate all higher ones
            // remove all non-permanent ones
            for (int i = 0; i < N; i++) {
                if (!inside[i]) {
                    active[i] = false;
                } else if (!permanent[i]) {
                    move_outside(x[i]);
                    no_inside--;
                    inside[i] = false;
                }
            }
        }
    }

    return low;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:103:41: warning: 'c_root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |                     move_inside(x[c_root]);
      |                                         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Incorrect 2 ms 208 KB Wrong answer.
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Incorrect 2 ms 208 KB Wrong answer.
8 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 21 ms 208 KB Output is correct
8 Incorrect 16 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -