Submission #977973

#	Time	Username	Problem	Language	Result	Execution time	Memory
977973		mircea_007	Rarest Insects (IOI22_insects)	C++17	99.56 / 100	34 ms	908 KiB

insects

#include "insects.h"
#include <vector>

// void move_inside(int i)
// void move_outside(int i)
// int press_button()

// gaseste numarul de valori distincte in N operatii
int dist_val( int N ) {
  std::vector<bool> rem( N, false );
  
  int ret = 0;
  for( int i = 0 ; i < N ; i++ ){
    move_inside( i );

    if( press_button() > 1 )
      move_outside( i );
    else{
      ret++;
      rem[i] = true;
    }
  }

  // cleanup
  for( int i = 0 ; i < N ; i++ )
    if( rem[i] )
      move_outside( i );

  return ret;
}

bool at_least_x( std::vector<int> &poz, int x, int dist ) {
  int n = (int)poz.size();
  std::vector<bool> rem( n, false );

  int good_poz = 0;
  for( int i = 0 ; i < n ; i++ ){
    move_inside( poz[i] );

    if( press_button() > x )
      move_outside( poz[i] );
    else{
      rem[i] = true;
      good_poz++;
    }
  }

  // cleanup
  for( int i = 0 ; i < n ; i++ )
    if( rem[i] )
      move_outside( poz[i] );

  bool decision = (good_poz == dist * x); // min(freq) >= x

  int news = 0;
  for( int i = 0 ; i < n ; i++ )
    if( rem[i] != decision )
      poz[news++] = poz[i];
  poz.erase( poz.begin() + news, poz.end() );

  return decision;
}

int min_cardinality( int N ) {
  int dist = dist_val( N );

  std::vector<int> poz;
  for( int i = 0 ; i < N ; i++ )
    poz.push_back( i );

  int st = 0, dr = N / dist + 1;
  while( dr - st > 1 ){
    int mij = (st + dr) >> 1;

    if( at_least_x( poz, mij - st, dist ) )
      st = mij;
    else
      dr = mij;
  }

  return st;
}

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