Submission #1243461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243461		sano	Rarest Insects (IOI22_insects)	C++20	57.92 / 100	40 ms	548 KiB

insects

#include "insects.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<long double, long double>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
/*
vec<int> original_pole;

set<int> masina;

void move_inside(int x) {
    masina.insert(x);
    return;
}

void move_outside(int x) {
    masina.erase(x);
    return;
}

int press_button() {
    unordered_map<int, int> umap;
    int maxi = 0;
    for (auto i : masina) {
        umap[original_pole[i]]++;
        maxi = max(maxi, umap[original_pole[i]]);
    }
    return maxi;
}*/

int dfs(int x, vec<int>& bol, vec<vec<int>>&g) {
    bol[x] = 1;
    int poc = 1;
    for (auto i : g[x]) {
        if (bol[i]) continue;
        poc += dfs(i, bol, g);
    }
    return poc;
}

void vyries(vec<int>& v, vec<int>& o, vec<vec<int>>& g) {
    if (v.size() == 0) return;
    if (v.size() == 1) {
        For(i, o.size()) {
            g[o[i]].push_back(v[0]);
            g[v[0]].push_back(o[i]);
        }
        move_outside(v[0]);
        return;
    }
    int l = 0;
    int r = v.size() - 1;
    int mid = (l + r) / 2;
    vec<int> v1, v2;
    For(i, mid + 1) {
        v1.push_back(v[i]);
    }
    for (int i = mid + 1; i < v.size(); i++) {
        v2.push_back(v[i]);
        move_outside(v[i]);
    }
    vec<int> o1, o2;
    for (int i = 0; i < o.size(); i++) {
        move_inside(o[i]);
        int x = press_button();
        move_outside(o[i]);
        if (x == 1) {
            o2.push_back(o[i]);
        }
        else {
            o1.push_back(o[i]);
        }
    }
    vyries(v1, o1, g);
    for (int i = mid + 1; i < v.size(); i++) {
        move_inside(v[i]);
    }
    vyries(v2, o2, g);
    return;
}

int min_cardinality(int n) {
    vec<vec<int>> g(n);
    vec<int> v;
    vec<int> o;
    For(i, n) {
        move_inside(i);
        int x = press_button();
        if (x == 1) {
            v.push_back(i);
        }
        else {
            o.push_back(i);
            move_outside(i);
        }
    }
    vyries(v, o, g);
    vec<int> bol(n, 0);
    int mini = n;
    For(i, n) {
        if (bol[i]) continue;
        mini = min(mini, dfs(i, bol, g));
    }
    return mini;
}

/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vec<int> p(n);
    For(i, n) cin >> p[i];
    original_pole = p;
    cout << min_cardinality(n) << '\n';
    return 0;
}
*/

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