제출 #691029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691029		CatalinT	Rarest Insects (IOI22_insects)	C++17	0 / 100	56 ms	448 KiB

insects

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <sstream>
#include <queue>

#include "insects.h"

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


using namespace std;

using int64 = long long;

int U;

int min_cardinality(int N) {
    set<int> inside;
    set<int> outside;

    for (int i = 0; i < N; i++) {
        move_inside(i);

        if (press_button() > 1) {
            move_outside(i);
            outside.insert(i);
        } else {
            inside.insert(i);
        }
    }

    U = size(inside);

    if (size(outside) < U) {
        return 1;
    }

    // cerr << "U: " << U << " / " << size(outside) << "\n";

    // binary search
    int l = 2, r = N / U;
    int sol = 1;

    while (l <= r) {
        int m = (l + r) >> 1;
        // cerr << "try: " << m << "\n";
        vector<int> first_half, second_half;
        bool ok = false;

        int rem = size(outside);

        for (auto c : outside) {

            // if ok then we can just add to second half
            if (ok) {
                second_half.push_back(c);
                continue;
            }

            // if it's the last try and we know we can't make it

            if (m == l + 1 && rem + size(inside) < m * U) {
                return sol;
            }

            move_inside(c);
            if (press_button() > m) {
                // c is second half
                move_outside(c);
                second_half.push_back(c);
                // cerr << c << " bad\n";
            } else {
                inside.insert(c);
                // cerr << c << " good\n";
                first_half.push_back(c);

                if (size(inside) == m * U) {
                    // min frequency >= m
                    ok = true;
                }
            }

            rem--;
        }

        // cerr << "ok: " << ok << "\n";

        if (ok) {
            // go m + 1 ... r
            // you don't need to remove anything
            sol = m;
            l = m + 1;
            cerr << size(second_half) << " / " << size(first_half) << "\n";
            outside = set<int>(begin(second_half), end(second_half));
        } else {
            // min frequency < m
            // gol ... m - 1
            // we need to remove every we added;
            for (auto c : first_half) {
                inside.erase(c);
                move_outside(c);
            }

            assert(size(inside) % U == 0);
            outside = set<int>(begin(first_half), end(first_half));
            r = m - 1;
            r = min(r, ((int)size(outside) + (int)size(inside)) / U);
        }

    }

    return sol;
}

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

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (size(outside) < U) {
      |         ~~~~~~~~~~~~~~^~~
insects.cpp:75:50: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |             if (m == l + 1 && rem + size(inside) < m * U) {
      |                               ~~~~~~~~~~~~~~~~~~~^~~~~~~
insects.cpp:90:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |                 if (size(inside) == m * U) {
      |                     ~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75