Submission #1069682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069682		j_vdd16	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	172 ms	928 KiB

insects

#include "insects.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

int n;
int lessThanK(int k) {
    vi notRemoved;
    loop(i, n) {
        move_inside(i);

        int res = press_button();
        if (res > k) {
            move_outside(i);
        }
        else {
            notRemoved.push_back(i);
        }
    }

    for (int x : notRemoved) {
        move_outside(x);
    }

    return notRemoved.size();
}

int min_cardinality(int _N) {
    n = _N;
    int l = 1, r = n;

    int lessThan1 = lessThanK(1);
    while (l < r) {
        int m = (l + r + 1) / 2;

        int lessThanM = lessThanK(m);
        if (lessThanM == lessThan1 * m) {
            l = m;
        }
        else {
            r = m - 1;
        }
    }

    return l;
    
    // vb isDone(N);

    // int diffCount = 0;
    // vb isNew(N);
    // loop(i, N) {
    //     move_inside(i);
        
    //     int res = press_button();
    //     if (res == 1) {
    //         diffCount++;
    //         isNew[i] = true;
    //     }
    //     else {
    //         move_outside(i);
    //     }
    // }
    // loop(i, N) {
    //     if (isNew[i]) {
    //         move_outside(i);
    //     }
    // }
    // int total = N;

    // while (true) {
    //     if (diffCount == 1) {
    //         return total;
    //     }

    //     int maxCount = 0;
    //     int lastIncrease = 0;
    //     loop(i, N) {
    //         if (isDone[i]) continue;

    //         move_inside(i);
    //         int res = press_button();
    //         if (res > maxCount) {
    //             maxCount = res;
    //             lastIncrease = i;
    //         }
    //     }

    //     if (diffCount == 2) {
    //         return total - maxCount;
    //     }

    //     vi possible;
    //     for (int x = 1; x <= total; x++) {
    //         // if (diffCount == 2 && x + maxCount != total) continue;
    //         // if (diffCount == 1 && (x != maxCount || x != total)) continue;

    //         if ((diffCount - 1) * x + maxCount <= total && total <= (diffCount - 1) * maxCount + x) {
    //             possible.push_back(x);
    //         }
    //     }

    //     if (possible.size() == 1) {
    //         return possible[0];
    //     }
    //     else if (possible.size() == 0) {
    //         return -1;
    //     }

    //     for (int i = N - 1; i > lastIncrease; i--) {
    //         if (isDone[i]) continue;

    //         move_outside(i);
    //     }

    //     vb isPartOfMax(N);
    //     isPartOfMax[lastIncrease] = true;
    //     for (int i = 0; i < lastIncrease; i++) {
    //         if (isDone[i]) continue;

    //         move_outside(i);
    //         int res = press_button();
    //         if (res < maxCount) {
    //             move_inside(i);
    //             isPartOfMax[i] = true;
    //         }
    //     }

    //     loop(i, N) {
    //         if (isPartOfMax[i]) {
    //             isDone[i] = true;
    //             move_outside(i);
    //         }
    //     }
        
    //     diffCount--;
    //     total -= maxCount;
    // }

    // return 0;
}

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