oj.uz

Submission #628859

# Submission time Handle Problem Language Result Execution time Memory
628859 2022-08-13T18:36:54 Z phathnv Rarest Insects (IOI22_insects) C++17
0 / 100
 2000 ms 208 KB 
#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;

bool isIn[MAX_N], nxt[MAX_N];
map<vector<int>, int> his;

int ask(const vector<int> &a) {
//    if (his.count(a)) {
//        return his[a];
//    }

    for (int i = 0; i < MAX_N; ++i) {
        nxt[i] = 0;
    }
    for (auto x : a) {
        nxt[x] = 1;
    }
    for (int i = 0; i < MAX_N; ++i) {
        if (isIn[i] > nxt[i]) {
            move_outside(i);
        }
        if (isIn[i] < nxt[i]) {
            move_inside(i);
        }
        isIn[i] = nxt[i];
    }
//    return his[a] = press_button();
    return press_button();
}

int min_cardinality(int n) {
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);

    vector<int> nxt, inside;
    for (auto x : a) {
        inside.push_back(x);
        if (ask(inside) > 1) {
            inside.pop_back();
            nxt.push_back(x);
        }
    }
    int numDistinct = inside.size();
    int res = 1;
    a = nxt;

    int l = 1, r = (int) a.size() / numDistinct;
    while (l <= r) {
        int mid = (l + r) >> 1;

        vector<int> outside;
        inside.clear();
        for (auto x : a) {
            inside.push_back(x);
            if (inside.size() == numDistinct * mid) {
                outside.push_back(x);
                continue;
            }
            if ((int)inside.size() <= mid) {
                continue;
            }
            if (ask(inside) > mid) {
                inside.pop_back();
                outside.push_back(x);
            }
        }
        if ((int)inside.size() == numDistinct * mid) {
            res += mid;
            a = outside;
            l = 1;
            r = (int)a.size() / numDistinct;
        } else {
            a = inside;
            l = max(1, (int)a.size() - mid * (numDistinct - 1));
            r = (int)a.size() / numDistinct;
        }
    }

    return res;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:59:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if (inside.size() == numDistinct * mid) {
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong answer.
2 Halted 0 ms 0 KB -