#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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
