Submission #836292

#	Time	Username	Problem	Language	Result	Execution time	Memory
836292		Trumling	Rarest Insects (IOI22_insects)	C++17	10 / 100	49 ms	404 KiB

insects

    #include "insects.h"
    #include<bits/stdc++.h>
    using namespace std;
     
    #define F first
    #define S second
    #define all(x) x.begin(),x.end()
    typedef long long ll;
    #define pb push_back
    #define INF 99999999999999
     
     
     
    int min_cardinality(int N) 
    {
      ll n=N;
      vector<int>type(n,-1);
      vector<int>count(n,1);
     
      ll ans=INF;
      set<int>s;
      vector<int>v;
      for(int i=0;i<N;i++)
        {
          move_inside(i);
          ll p=press_button();
          if(p!=1)
          move_outside(i);
          else
          {
          type[i]=i;
          v.pb(i);
          }
        }

       for(int i=0;i<N;i++)
       move_outside(i);

      for(int i=0;i<N;i++)
        if(type[i]==-1)
        {
          ll l=0,r=v.size()-1;
          move_inside(i);
          while(l<r)
          {
            ll mid=(l+r)/2;
     
            for(int j=l;j<=mid;j++)
            move_inside(v[j]);
     
            ll p=press_button();
            
            for(int j=l;j<=mid;j++)
            move_outside(v[j]);
     
            if(p!=1)
            r=mid;
            else
            l=mid+1;
            
          }
          move_outside(i);
          count[v[l]]++;
        }
     
      for(auto x:v)
      ans=min(ans,(ll)count[x]);
      
      return ans;
    }

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