oj.uz

Submission #998480

# Submission time Handle Problem Language Result Execution time Memory
998480 2024-06-14T03:55:43 Z kym Rarest Insects (IOI22_insects) C++17
0 / 100
 255 ms 848 KB 
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> head;
set<int>in;
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);
    }
  }
  for(auto x:head)move_outside(x);
  int sum = N;
  while(head.size() > 1){
    //cerr<<head.size()<<endl;
    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()){
        in.insert(x);
        move_inside(x);
        int res=press_button();
        if(res == L){
          toerase.insert(x);
          move_outside(x);
          in.erase(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);
      }
      //cerr << L<<":"<<have<<endl;
    }
    //cerr << L<<":"<<have<<endl;
    if(!have) return L;
    for(auto x:rmvhead)head.erase(x);
    for(auto x:toerase)active.erase(x);
    for(auto x:in)move_outside(x);
    in.clear();
  }
  return sum;
  assert(0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 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 2 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Incorrect 239 ms 344 KB Too many queries.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 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 2 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Incorrect 239 ms 344 KB Too many queries.
10 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 1 ms 344 KB Output is correct
7 Correct 9 ms 500 KB Output is correct
8 Correct 19 ms 632 KB Output is correct
9 Correct 16 ms 756 KB Output is correct
10 Incorrect 255 ms 848 KB Too many queries.
11 Halted 0 ms 0 KB -