Submission #836303

#	Time	Username	Problem	Language	Result	Execution time	Memory
836303		Trumling	Rarest Insects (IOI22_insects)	C++17	10 / 100	82 ms	356 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(auto x:v)
      move_outside(x);

      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++)
            {
              if(s.find(v[j])==s.end())
              move_inside(v[j]);
              s.insert(v[j]);
            }
     
            ll p=press_button();
            
            
     
            if(p!=1)
            {
            r=mid;
            for(int j=(l+r)/2+1;j<=r;j++)
            {
              move_outside(v[j]);
              s.erase(v[j]);
            }
            
            }
            else
            l=mid+1;
            
          }

          for(auto itr=s.begin();itr!=s.end();itr++)
          move_outside(*itr);
          s.clear();

          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