Submission #1212671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212671		qwusha	Rarest Insects (IOI22_insects)	C++20	60.15 / 100	42 ms	528 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e9;

/*
vector<int> A;
set<int> ST;

void move_inside(int i) {
    ST.insert(i);
}

void move_outside(int i) {
    ST.erase(i);
}

int press_button() {
    vector<int> count(100);
    int maxi = 0;
    for (auto el: ST) {
        count[A[el]]++;
        maxi = max(maxi, count[A[el]]);
    }
    return maxi;
}*/


int min_cardinality(int n) {
    vector<int> par(n, -1);
    vector<int> sex(n, 1);
    par[0] = 0;
    int boss = 1;
    move_inside(0);
    set<int> cool = {0};
    sex[0] = 0;
    for (int i = 1; i < n; i++) {
        move_inside(i);
        int x = press_button();
        if (x != 1) {
            move_outside(i);
        } else {
            par[i] = i;
            sex[i] = 0;
            boss++;
            cool.insert(i);
        }
    }
    for (auto el : cool) {
        move_outside(el);
    }
    if (boss < 16) {
        int mini = inf;
        for (auto st : cool) {
            move_inside(st);
            int cur = 1;
            for (int i = st + 1; i < n; i++) {
                if (cur >= mini) {
                    break;
                }
                if (par[i] == -1) {
                    move_inside(i);
                    int x = press_button();
                    if (x == cur) {
                        move_outside(i);
                    } else {
                        cur = x;
                        par[i] = st;
                    }
                }
            }
            mini = min(mini, cur);
            for (int i = 0; i < n; i++) {
                if (par[i] == st) {
                    move_outside(i);
                }
            }
        }
        return mini;
    } else {
        int l = 1;
        int r = 127;
        while (r - l > 1) {
            set<int> nco = {};
            int mid1 = l + 1;
            int mid2 = (l + r) / 2;
            int mid = mid1 + (rnd() % (mid2 - mid1 + 1));
            for (int i = 0; i < n; i++) {
                if (sex[i] == 0) {
                    continue;
                }
                move_inside(i);
                int x = press_button();
                if (x > (mid - l)) {
                    move_outside(i);
                } else {
                    nco.insert(i);
                }
            }
            if (boss * (mid - l) == nco.size()) {
                l = mid;
                for (auto el : nco) {
                    sex[el] = 0;
                    move_outside(el);
                }
            } else {
                r = mid;
                for (int i = 0; i < n; i++) {
                    if (nco.find(i) == nco.end()) {
                        sex[i] = 0;
                    }
                }
                for (auto el : nco) {
                    move_outside(el);
                }
            }
        }
        int res = l;
        return res;
    }
}

/*
int correct(int n) {
    vector<int> par(n, -1);
    par[0] = 0;
    int boss = 1;
    move_inside(0);
    set<int> cool = {0};
    for (int i = 1; i < n; i++) {
        move_inside(i);
        int x = press_button();
        if (x != 1) {
            move_outside(i);
        } else {
            par[i] = i;
            boss++;
            cool.insert(i);
        }
    }
    for (auto el : cool) {
        move_outside(el);
    }
    if (boss < 8) {
        int mini = inf;
        for (auto st : cool) {
            move_inside(st);
            int cur = 1;
            for (int i = st + 1; i < n; i++) {
                if (cur >= mini) {
                    break;
                }
                if (par[i] == -1) {
                    move_inside(i);
                    int x = press_button();
                    if (x == cur) {
                        move_outside(i);
                    } else {
                        cur = x;
                        par[i] = st;
                    }
                }
            }
            mini = min(mini, cur);
            for (int i = 0; i < n; i++) {
                if (par[i] == st) {
                    move_outside(i);
                }
            }
        }
        return mini;
    } else {
        int l = 1;
        int r = 252;
        while (r - l > 1) {
            set<int> nco = {};
            int mid = (l + r) / 2;
            for (int i = 0; i < n; i++) {
                move_inside(i);
                int x = press_button();
                if (x > mid) {
                    move_outside(i);
                } else {
                    nco.insert(i);
                }
            }
            if (boss * mid == nco.size()) {
                l = mid;
            } else {
                r = mid;
            }
            for (auto el : nco) {
                move_outside(el);
            }
        }
        int res = l;
        return res;
    }
}


signed main() {
    int SIZIK = 100;
    A.resize(SIZIK);
    for (int i = 0; i < 500; i++) {
        for (int j = 0; j < SIZIK; j++) {
            A[j] = rnd() % 4;
        }
        int cor = correct(SIZIK);
        ST.clear();
        int mine = min_cardinality(SIZIK);
        if (cor != mine) {
            cout << "FAIL" << endl;
            cout << "CORRECT: " << cor << "    MINE: " << mine << endl;
            cout << "A:   ";
            for (auto el : A) {
                cout << el << ", " ;
            }
            cout << endl;
            return 0;
        }
        ST.clear();
    }
    cout << "SUCCESS" << endl;
}
 */

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