Submission #1339325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339325		limits	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	16 ms	460 KiB

insects

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;

#include "insects.h"

int cnt = 0;

vi act, acc, rej;

int exe(int k, int N) {
	random_shuffle(all(act));
	rej = acc = {};
	forl(x, act) {
		move_inside(x);
		if (press_button() > k) {
			move_outside(x);
			rej.pb(x);
		} else {
			cnt += 1;
			acc.pb(x);
		}
	}
	return cnt;
}

int min_cardinality(int N) {
	cnt = 0;
	act = acc = rej = {};

	f0r(i, N) act.pb(i);
	int D = exe(1, N);
	act = rej;
	//ctl(rej);
	//return 0;

	int lo = 2, hi = N/D, ans = 1;
	while (lo <= hi) {
		int m = (lo + hi)/2;
		//cout << m << endl;

		int C = exe(m, N);
		//cout << C << endl;
		if (C == D*m) {
			lo = m+1;
			ans = m;
			act = rej;
		} else {
			hi = m-1;
			if (hi < lo) break;
			forl(x, acc) {
				move_outside(x);
				--cnt;
			}
			act = acc;
		}
	}
	//cout << "ANS: " << ans << endl;

	return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int exe(int, int)':
insects.cpp:38:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   38 |         random_shuffle(all(act));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from insects.cpp:4:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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