oj.uz

Submission #998476

# Submission time Handle Problem Language Result Execution time Memory
998476 2024-06-14T03:48:32 Z kym Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 344 KB 
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> head;
int min_cardinality(int N) {
  set<int>active;
  for(int i=0;i<N;i++){
    active.insert(i);
    move_inside(i);
    int res=press_button();
    if(res == 1){
      head.insert(i);
      move_outside(i);
    } else{
      move_outside(i);
    }
  }
  int sum = N;
  while(head.size() > 1){
    int L = (int)sum / (int)head.size() ;
    // we will be keeping the groups that are < L only
    set<int> toerase;
    set<int>rmvhead;
    for(auto x:active){
      if(head.find(x) == head.end()){
        move_inside(x);
        int res=press_button();
        if(res == L){
          toerase.insert(x);
          move_outside(x);
          sum --;
        }
      } else{
        continue;
      }
    }
    bool have=0;
    for(auto x:head){
      move_inside(x);
      int res=press_button();
      if(res == L){
        toerase.insert(x);
        rmvhead.insert(x);
        move_outside(x);
        sum-=L;
      } else{
        have = 1;
        move_outside(x);
      }
    }
    if(!have) return L;
    for(auto x:rmvhead)head.erase(x);
    for(auto x:toerase)active.erase(x);
  }
  assert(0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong answer.
2 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 Incorrect 1 ms 344 KB Wrong answer.
3 Halted 0 ms 0 KB -