Submission #722488

#	Time	Username	Problem	Language	Result	Execution time	Memory
722488		bin9638	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	66 ms	544 KiB

insects

#include <bits/stdc++.h>

#ifndef SKY
#include "insects.h"
#endif // SKY

using namespace std;

#define N 2010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int n;

#ifdef SKY
int type[N],chon[N],cnt[N];

void move_inside(int i)
{
    chon[i]=1;
}

void move_outside(int i)
{
    chon[i]=0;
}

int press_button()
{
    int res=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<n;i++)
        if(chon[i]==1)
            res=max(res,++cnt[type[i]]);
    return res;
}
#endif // SKY

int dp[N],ktr[N],sl,ans=1;
vector<int>s,luu;

bool check(int x)
{
    luu=s;
    int val=ans;
    for(int i=0;i<n;i++)
        if(ktr[i]==0&&dp[i]<=x)
        {
            move_inside(i);
            int t=press_button();
            if(t==x+1)
            {
                move_outside(i);
                dp[i]=max(dp[i],x+1);
                continue;
            }
            luu.pb(i);
            if(t==val+1)
            {
                val=t;
                dp[i]=max(dp[i],t);
            }
        }
    return(luu.size()==x*sl);
}

int min_cardinality(int NNN)
{
  n=NNN;
  for(int i=0;i<n;i++)
  {
      move_inside(i);
      if(press_button()<=1)
      {
          s.pb(i);
          ktr[i]=1;
      }else
      {
          move_outside(i);
      }
  }
  sl=s.size();
  if(sl==1)
    return n;
  if(sl*2>n)
    return 1;
  int l=2,r=n/sl;
  while(l<=r)
  {
      int mid=(l+r)/2;
      if(check(mid))
      {
          ans=mid;
          l=mid+1;
          s=luu;
          for(auto i:s)
                ktr[i]=1;
      }else
      {
          while(luu.back()!=s.back())
          {
              move_outside(luu.back());
              luu.pop_back();
          }
          r=mid-1;
      }
  }
  return ans;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>type[i];
    cout<<min_cardinality(n);
    return 0;
}
#endif

Compilation message (stderr)

insects.cpp: In function 'bool check(int)':
insects.cpp:67:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     return(luu.size()==x*sl);
      |            ~~~~~~~~~~^~~~~~

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