Submission #755132

#	Time	Username	Problem	Language	Result	Execution time	Memory
755132		Rafi22	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	85 ms	448 KiB

insects

#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,S;
    bool is=0;
    for(auto x:a)
    {
        if(Z>=0)
        {
            move_inside(x);
            if(press_button()>k)
            {
                move_outside(x);
                Z--;
                N.pb(x);
            }
            else T.pb(x);
        }
        else S.pb(x);
    }
    for(auto x:T) move_outside(x);
    for(auto x:S) T.pb(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)

insects.cpp:102:1: warning: "/*" within comment [-Wcomment]
  102 | /*
      |  
insects.cpp: In function 'void rek(std::vector<int>)':
insects.cpp:46:10: warning: unused variable 'is' [-Wunused-variable]
   46 |     bool is=0;
      |          ^~

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