oj.uz

Submission #627592

# Submission time Handle Problem Language Result Execution time Memory
627592 2022-08-12T17:25:00 Z Tigerpants Rarest Insects (IOI22_insects) C++17
0 / 100
 6 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) {
    vb roots(N, false);
    vb inside(N, false);
    vb permanent(N, false);

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

    for (int i = 1; i < N; i++) {
        move_inside(i);
        inside[i] = true;
        if (press_button() == 2) {
            move_outside(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;
    }

    int no_inside = no_roots;
    
    int high = (N / no_roots) + 1;
    int low = 1;
    while (low + 1 < high) {
        int middle = (low + high) / 2;
        for (int i = 0; i < N; i++) {
            if ((!inside[i]) && (active[i])) {
                move_inside(i);
                inside[i] = true;
                no_inside++;
                if (press_button() > middle) {
                    move_outside(i);
                    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(i);
                    inside[i] = false;
                }
            }
        }
    }

    return low;
}

Subtask #1
0 / 10.0

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