Submission #954025

#	Time	Username	Problem	Language	Result	Execution time	Memory
954025		ALTAKEXE	드문 곤충 (IOI22_insects)	C++17	Compilation error	0 ms	0 KiB

insects

#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<ll, ll> 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());
ll Random(ll l, ll r) {
    return uniform_int_distribution<int>(l, r)(rng);
}
 
const bool isMultiTest = 0;
const int MAXN = 2003;
 
struct Jury {
    set<ll> Set;
    multiset<ll> mCnt;
    vector<ll> type;
    map<ll, ll> Map;
 
    void init(ll _N) {
        type.resize(_N);
        for (ll i = 0; i < _N; ++i) {
            cin >> type[i];
            type[i] = Random(1, 100); cout << type[i] << " \n"[i + 1 == _N];
        }
    }
 
    void move_inside(ll i) {
        if(Set.find(i) == Set.end()) {
            ll &Mapt(Map[type[i]]);
            if(Mapt > 0)
                mCnt.erase(mCnt.find(Mapt));
 
            mCnt.insert(++Mapt);
            Set.insert(i);
        }
    }
 
    void move_outside(ll i) {
        if(Set.find(i) != Set.end()) {
            ll &Mapt(Map[type[i]]);
            mCnt.erase(mCnt.find(Mapt));
            if(--Mapt > 0)
                mCnt.insert(Mapt);
 
            Set.erase(i);
        }
    }
 
    ll press_button(void) {
        return *mCnt.rbegin();
    }
 
    ll answer(void) {
        ll ans(sz(type));
        for (ll i = 0; i < sz(type); ++i) {
            ll cnt(0);
            for (ll j = 0; j < sz(type); ++j)
                cnt += (type[i] == type[j]);
 
            ans = min(ans, cnt);
        }
 
        return ans;
    }
 
} jury;
 
vector<ll> id;
ll size_in_machine, nArr;
bool dx[MAXN], dx_in[MAXN], dx_out[MAXN];
 
ll cnt_move_inside, cnt_move_outside, cnt_press_button;
void ask_move_inside(ll 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(ll 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
}
 
ll ask_press_button(void) {
    ++cnt_press_button;
    #ifdef Nhoksocqt1
        return jury.press_button();
    #else
        return press_button();
    #endif // Nhoksocqt1
}
 
bool check(ll x, ll k) {
    for (ll 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 (ll i = 0; i < nArr; ++i) {
        if(!dx[i])
            dx_out[i] = 1;
 
        if(dx[i] && !dx_in[i])
            ask_move_outside(i);
    }
 
    return false;
}
 
ll min_cardinality(ll _N) {
    nArr = _N;
 
    id.clear();
    for (ll i = 0; i < nArr; ++i)
        id.push_back(i);
 
    shuffle(id.begin(), id.end(), rng);
    size_in_machine = 0;
 
    vector<ll> uniqueType;
    for (ll 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 (ll i = 0; i < nArr; ++i) {
        if(!dx[i])
            ask_move_inside(i);
    }
 
    ll max_cardinality = ask_press_button();
    if(max_cardinality == nArr)
        return max_cardinality;
 
    if(sz(uniqueType) == 2)
        return nArr - max_cardinality;
 
    for (ll i = 0; i < nArr; ++i) {
        if(dx[i] && !dx_in[i])
            ask_move_outside(i);
    }
 
    ll 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;
}
 

Compilation message (stderr)

insects.cpp:200: error: unterminated #ifdef
  200 | #ifdef Nhoksocqt1
      | 
insects.cpp: In function 'void ask_move_inside(ll)':
insects.cpp:90:9: error: 'move_inside' was not declared in this scope; did you mean 'ask_move_inside'?
   90 |         move_inside(i);
      |         ^~~~~~~~~~~
      |         ask_move_inside
insects.cpp: In function 'void ask_move_outside(ll)':
insects.cpp:101:9: error: 'move_outside' was not declared in this scope; did you mean 'ask_move_outside'?
  101 |         move_outside(i);
      |         ^~~~~~~~~~~~
      |         ask_move_outside
insects.cpp: In function 'll ask_press_button()':
insects.cpp:110:16: error: 'press_button' was not declared in this scope; did you mean 'ask_press_button'?
  110 |         return press_button();
      |                ^~~~~~~~~~~~
      |                ask_press_button