제출 #628859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628859		phathnv	드문 곤충 (IOI22_insects)	C++17	0 / 100	3073 ms	208 KiB

insects

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75