#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
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
