# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
755128 | Rafi22 | Rarest Insects (IOI22_insects) | C++17 | 60 ms | 316 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 "insects.h"
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
int ans=1,m;
/*
int a[107];
map<int,int>ile;
set<int>W;
void move_inside(int i)
{
W.insert(i);
}
void move_outside(int i)
{
W.erase(i);
}
int press_button()
{
ile.clear();
int ans=0;
for(auto x:W) ans=max(ans,++ile[a[x]]);
return ans;
}
*/
void rek(vector<int>a)
{
if(sz(a)<m) return ;
int k=(sz(a)/m+1)/2;
int Z=sz(a)-m*k;
vector<int>T,N;
bool is=0;
for(auto x:a)
{
if(Z<0) break;
move_inside(x);
if(press_button()>k)
{
move_outside(x);
Z--;
N.pb(x);
}
else T.pb(x);
}
for(auto x:T) move_outside(x);
if(sz(T)==m*k)
{
ans+=k;
rek(N);
}
else rek(T);
}
int min_cardinality(int n)
{
vector<int>V,X;
for(int i=0;i<n;i++)
{
move_inside(i);
if(press_button()>1)
{
move_outside(i);
V.pb(i);
}
else
{
X.pb(i);
m++;
}
}
for(auto x:X) move_outside(x);
rek(V);
return ans;
}
/*
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cout<<min_cardinality(n)<<endl;
return 0;
}
/*
6
5 8 9 5 9 9
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |