제출 #948047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948047		Nhoksocqt1	드문 곤충 (IOI22_insects)	C++17	94.95 / 100	39 ms	856 KiB

insects

#ifndef Nhoksocqt1
    #include "insects.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const bool isMultiTest = 0;
const int MAXN = 2003;

struct Jury {
    set<int> Set;
    multiset<int> mCnt;
    vector<int> type;
    map<int, int> Map;

    void init(int _N) {
        type.resize(_N);
        for (int i = 0; i < _N; ++i) {
            cin >> type[i];
            type[i] = Random(1, 100); cout << type[i] << " \n"[i + 1 == _N];
        }
    }

    void move_inside(int i) {
        if(Set.find(i) == Set.end()) {
            int &Mapt(Map[type[i]]);
            if(Mapt > 0)
                mCnt.erase(mCnt.find(Mapt));

            mCnt.insert(++Mapt);
            Set.insert(i);
        }
    }

    void move_outside(int i) {
        if(Set.find(i) != Set.end()) {
            int &Mapt(Map[type[i]]);
            mCnt.erase(mCnt.find(Mapt));
            if(--Mapt > 0)
                mCnt.insert(Mapt);

            Set.erase(i);
        }
    }

    int press_button(void) {
        return *mCnt.rbegin();
    }

    int answer(void) {
        int ans(sz(type));
        for (int i = 0; i < sz(type); ++i) {
            int cnt(0);
            for (int j = 0; j < sz(type); ++j)
                cnt += (type[i] == type[j]);

            ans = min(ans, cnt);
        }

        return ans;
    }

} jury;

vector<int> id;
int size_in_machine, nArr;
bool dx[MAXN], dx_in[MAXN], dx_out[MAXN];

int cnt_move_inside, cnt_move_outside, cnt_press_button;
void ask_move_inside(int i) {
    dx[i] = 1, i = id[i];
    ++size_in_machine;
    ++cnt_move_inside;
    #ifdef Nhoksocqt1
        jury.move_inside(i);
    #else
        move_inside(i);
    #endif // Nhoksocqt1
}

void ask_move_outside(int i) {
    dx[i] = 0, i = id[i];
    --size_in_machine;
    ++cnt_move_outside;
    #ifdef Nhoksocqt1
        jury.move_outside(i);
    #else
        move_outside(i);
    #endif // Nhoksocqt1
}

int ask_press_button(void) {
    ++cnt_press_button;
    #ifdef Nhoksocqt1
        return jury.press_button();
    #else
        return press_button();
    #endif // Nhoksocqt1
}

bool check(int x, int k) {
    for (int i = 0; i < nArr; ++i) {
        if(dx[i] || dx_out[i])
            continue;

        ask_move_inside(i);
        if(size_in_machine > x && ask_press_button() > x)
            ask_move_outside(i);
    }

    int res = size_in_machine;
    if(res / x == k) {
        for (int i = 0; i < nArr; ++i) {
            if(dx[i])
                dx_in[i] = 1;
        }

        return true;
    }

    for (int i = 0; i < nArr; ++i) {
        if(!dx[i])
            dx_out[i] = 1;

        if(dx[i] && !dx_in[i])
            ask_move_outside(i);
    }

    return false;
}

int min_cardinality(int _N) {
    nArr = _N;

    id.clear();
    for (int i = 0; i < nArr; ++i)
        id.push_back(i);

    shuffle(id.begin(), id.end(), rng);
    size_in_machine = 0;

    vector<int> uniqueType;
    for (int i = 0; i < nArr; ++i) {
        ask_move_inside(i);
        uniqueType.push_back(i);
        dx_in[i] = 1;

        if(size_in_machine > 1 && ask_press_button() > 1) {
            ask_move_outside(i);
            uniqueType.pop_back();
            dx_in[i] = 0;
        }
    }

    for (int i = 0; i < nArr; ++i) {
        if(!dx[i])
            ask_move_inside(i);
    }

    int max_cardinality = ask_press_button();
    if(max_cardinality == nArr)
        return max_cardinality;

    if(sz(uniqueType) == 2)
        return nArr - max_cardinality;

    if(sz(uniqueType) == nArr || nArr - max_cardinality < 2 * sz(uniqueType))
        return 1;

    for (int i = 0; i < nArr; ++i) {
        if(dx[i] && !dx_in[i])
            ask_move_outside(i);
    }

    int l(2), r = min(max_cardinality, nArr - max_cardinality - sz(uniqueType) + 2), ans(1);
    r = min(r, (nArr - max_cardinality) / (sz(uniqueType) - 1));

    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid, sz(uniqueType))) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return ans;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "insects"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int N;
    cin >> N;
    jury.init(N);

    int ans = min_cardinality(N);
    cout << "ANSWER: " << ans << '\n';
    cout << "JURY ANSWER: " << jury.answer() << '\n';
    cout << "CNT MOVE INSIDE: " << cnt_move_inside << '\n';
    cout << "CNT MOVE OUTSIDE: " << cnt_move_outside << '\n';
    cout << "CNT PRESS BUTTON: " << cnt_press_button << '\n';

    cnt_move_inside = cnt_move_outside = cnt_press_button = 0;

    return 0;
}

#endif // Nhoksocqt1

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