제출 #731986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731986		alextodoran	Rarest Insects (IOI22_insects)	C++17	89.96 / 100	127 ms	420 KiB

insects

/**

 /\      /\
 \_\_//_/_/
  / 0  0  \
  \  /   \/
  /____ \/ \
  (o  o)/ \
   \__/\ \

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int min_cardinality (int N) {
    bool in[N];
    int id[N];
    fill(in, in + N, false);
    int dist = 0;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            in[i] = true;
            id[i] = dist++;
        }
    }
    if (dist <= 6) {
        int occ[dist];
        fill(occ, occ + dist, 0);
        for (int i = 0; i < N; i++) {
            if (in[i] == false) {
                move_inside(i);
                for (int j = 0; j < N; j++) {
                    if (in[j] == true) {
                        move_outside(j);
                        if (press_button() == 1) {
                            in[j] = false;
                            id[i] = id[j];
                            break;
                        }
                        move_inside(j);
                    }
                }
                in[i] = true;
            }
            occ[id[i]]++;
        }
        int mn = N;
        for (int i = 0; i < dist; i++) {
            mn = min(mn, occ[i]);
        }
        return mn;
    }
    if (dist == N) {
        return 1;
    }
    int A = 3, B = 1;
    bool bad[N];
    fill(bad, bad + N, false);
    int cnt = dist;
    int l = 1, r = N / dist;
    while (l < r) {
        int k = (l * A + r * B + A + B - 1) / (A + B);
        vector <int> v1, v2;
        for (int i = 0; i < N; i++) {
            int suff = 0;
            for (int j = i; j < N; j++) {
                if (in[j] == false && bad[j] == false) {
                    suff++;
                }
            }
            if (cnt + suff < dist * k) {
                break;
            }
            if (in[i] == false && bad[i] == false) {
                move_inside(i);
                if (press_button() > k) {
                    move_outside(i);
                    bad[i] = true;
                    v1.push_back(i);
                } else {
                    in[i] = true;
                    v2.push_back(i);
                    cnt++;
                }
            }
        }
        if (cnt == dist * k) {
            l = k;
            for (int i : v1) {
                bad[i] = false;
            }
        } else {
            r = k - 1;
            for (int i : v2) {
                move_outside(i);
                in[i] = false;
                cnt--;
            }
        }
    }
    return l;
}

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