oj.uz

Submission #977966

# Submission time Handle Problem Language Result Execution time Memory
977966 2024-05-08T15:09:15 Z mircea_007 Rarest Insects (IOI22_insects) C++17
0 / 100
 24 ms 660 KB 
#include "insects.h"
#include <vector>

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

const int MAXN = 5000;

// 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() >= 2 )
      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++ ){
    int idx = poz[i];
    
    move_inside( idx );
    if( press_button() > x ){
      move_outside( idx );
    }else{
      rem[i] = true;
      good_poz++;
    }
  }

  // cleanup
  for( int i = 0 ; i < n ; i++ )
    if( rem[poz[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
0 / 10.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 75.0

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