oj.uz

Submission #836298

# Submission time Handle Problem Language Result Execution time Memory
836298 2023-08-24T09:52:43 Z Trumling Rarest Insects (IOI22_insects) C++17
0 / 100
 56 ms 552 KB 
    #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++)
            move_inside(v[j]);
     
            ll p=press_button();
            
            
     
            if(p!=1)
            {
            r=mid;
            for(int j=l;j<=mid;j++)
            move_outside(v[j]);
            }
            
            else
            l=mid+1;
            
          }
          move_outside(i);
          count[v[l]]++;
        }
     
      for(auto x:v)
      ans=min(ans,(ll)count[x]);
      
      return ans;
    }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 7 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Incorrect 7 ms 208 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 19 ms 296 KB Output is correct
8 Correct 10 ms 552 KB Output is correct
9 Incorrect 56 ms 208 KB Too many queries.
10 Halted 0 ms 0 KB -