답안 #954036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954036 2024-03-27T06:37:24 Z ALTAKEXE 드문 곤충 (IOI22_insects) C++17
컴파일 오류
0 ms 0 KB
#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);

        if (size_in_machine / 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;

    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;
}

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;
}

Compilation message

insects.cpp: In function 'void ask_move_inside(int)':
insects.cpp:104:5: error: 'move_inside' was not declared in this scope; did you mean 'ask_move_inside'?
  104 |     move_inside(i);
      |     ^~~~~~~~~~~
      |     ask_move_inside
insects.cpp: In function 'void ask_move_outside(int)':
insects.cpp:116:5: error: 'move_outside' was not declared in this scope; did you mean 'ask_move_outside'?
  116 |     move_outside(i);
      |     ^~~~~~~~~~~~
      |     ask_move_outside
insects.cpp: In function 'int ask_press_button()':
insects.cpp:126:12: error: 'press_button' was not declared in this scope; did you mean 'ask_press_button'?
  126 |     return press_button();
      |            ^~~~~~~~~~~~
      |            ask_press_button
insects.cpp: In function 'int main()':
insects.cpp:237:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
insects.cpp:238:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~