| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 636542 | MohamedAliSaidane | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef long double ld;
//#define int ll
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define pp pop_back
#define pf push_front
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
int nx[8] = {0,0,1,-1, 1, 1, -1, -1}, ny[8] = {1,-1,0,0, 1, -1, 1, -1};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
const ll MOD = 1e9 + 7;
ll mod(ll x, ll m = MOD){return (x + m)%m;}
/*
int press_button();
void move_inside(int i );
void move_outside(int i);
*/
int min_cardinality(int n)
{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int T = 0;
set<int> machine;
for(int i = 0; i < n; i++)
{
move_inside(i);
machine.insert(i);
if(press_button() > 1)
{
machine.erase(i);
move_outside(i);
}
else
{
T++;
}
}
if(T == n)
return 1;
if(T == 1)
return n;
set<int> vis;
vis.insert(1); vis.insert(n);
vi s[n + 1];
for(auto e: machine)
s[1].pb(e);
for(int i = 0; i < n; i++)
s[n].pb(i);
int debut = 2;
int fin = n/T;
int rep = 1;
while(debut <= fin)
{
int mid = (debut + fin)/2;
int nxt = *(vis.lower_bound(mid));
set<int> just_added ;
int cnt = 0;
shuffle(all(s[nxt]), rng);
for(auto e: s[nxt])
{
if(machine.count(e) == 0)
{
move_inside(e);
machine.insert(e);
if(press_button() > mid)
{
move_outside(e);
machine.erase(e);
}
else
{
just_added.insert(e);
cnt++;
}
}
else
cnt++;
}
vis.insert(mid);
for(auto e: machine)
s[mid].pb(e);
if(cnt >= mid * T)
{
rep = mid;
debut = mid + 1;
}
else
{
fin = mid - 1;
for(auto e: just_added)
machine.erase(e), move_outside(e);
}
}
return rep;
}
/*
static inline constexpr int kMaxQueries = 40000;
static int N;
// Insect types are compressed to colors in the range [0, N).
static std::vector<int> color;
static std::vector<bool> in_box;
static std::vector<int> color_occurrences;
static std::multiset<int> max_occurrences;
static std::vector<int> op_counter(3, 0);
static inline void protocol_violation(std::string message) {
printf("Protocol Violation: %s\n", message.c_str());
exit(0);
}
void move_inside(int i) {
if (i < 0 || i >= N) {
protocol_violation("invalid parameter");
}
++op_counter[0];
if (op_counter[0] > kMaxQueries) {
protocol_violation("too many calls");
}
if (!in_box[i]) {
in_box[i] = true;
max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
++color_occurrences[color[i]];
max_occurrences.insert(color_occurrences[color[i]]);
}
}
void move_outside(int i) {
if (i < 0 || i >= N) {
protocol_violation("invalid parameter");
}
++op_counter[1];
if (op_counter[1] > kMaxQueries) {
protocol_violation("too many calls");
}
if (in_box[i]) {
in_box[i] = false;
max_occurrences.erase(max_occurrences.find(color_occurrences[color[i]]));
--color_occurrences[color[i]];
max_occurrences.insert(color_occurrences[color[i]]);
}
}
int press_button() {
++op_counter[2];
if (op_counter[2] > kMaxQueries) {
protocol_violation("too many calls");
}
return *(max_occurrences.rbegin());
}
int main() {
assert(1 == scanf("%d", &N));
color.resize(N);
in_box.assign(N, false);
std::map<int, int> type_to_color;
for (int i = 0; i < N; ++i) {
int Ti;
assert(1 == scanf("%d", &Ti));
if (type_to_color.find(Ti) == type_to_color.end()) {
int new_color = type_to_color.size();
type_to_color[Ti] = new_color;
max_occurrences.insert(0);
}
color[i] = type_to_color[Ti];
}
color_occurrences.assign(type_to_color.size(), 0);
int answer = min_cardinality(N);
int Q = *std::max_element(op_counter.begin(), op_counter.end());
printf("%d\n", answer);
printf("%d\n", Q);
return 0;
}
/*
*/