oj.uz

Submission #980448

# Submission time Handle Problem Language Result Execution time Memory
980448 2024-05-12T07:31:41 Z CSQ31 Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 344 KB 
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int>dis,unknown,id;
int type[2222];
void solve(int l,int r,vector<int>v){
  if(v.empty())return;
  if(l==r){
      for(int x:v)type[x] = type[dis[l]];
      return;
  }

  int tm = (l+r)/2;
  for(int i=tm+1;i<=r;i++){
      move_outside(id[v[i]]);
  }
  vector<int>a,b;
  for(int x:v){
      move_inside(id[x]);
      if(press_button() == 2)a.push_back(x);
      else b.push_back(x);
      move_outside(id[x]);
  }
  solve(l,tm,a);
  if(!b.empty()){
      for(int i=tm+1;i<=r;i++)move_inside(id[dis[i]]);
      solve(tm+1,r,b);
  }
}
int min_cardinality(int N) {
  for(int i=0;i<N;i++)id.push_back(i);
  random_shuffle(id.begin(),id.end());

  for(int i=0;i<N;i++){
      move_inside(id[i]);
      if(press_button() != 1){
          move_outside(id[i]);
          unknown.push_back(i);
        }else{
          dis.push_back(i);
          type[i] = sz(dis);
        }
  }
  solve(0,sz(dis)-1,unknown);
  vector<int>cnt(N+1,0);
  int mn = N;
  for(int i=0;i<N;i++)cnt[type[i]]++;
  for(int i=1;i<=sz(dis);i++)mn = min(mn,cnt[i]);
  return mn;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 0 ms 344 KB Wrong answer.
5 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 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB Wrong answer.
5 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 1 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Wrong answer.
7 Halted 0 ms 0 KB -