oj.uz

Submission #980453

# Submission time Handle Problem Language Result Execution time Memory
980453 2024-05-12T07:38:02 Z CSQ31 Rarest Insects (IOI22_insects) C++17
0 / 100
 0 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[dis[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);
  for(int i=tm+1;i<=r;i++)move_inside(id[dis[i]]);
  if(!b.empty()){
      solve(tm+1,r,b);
  }
}
int min_cardinality(int N) {
  for(int i=0;i<N;i++)id.push_back(i);
  shuffle(id.begin(),id.end(),seed);

  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++)cout<<type[i]<<" ";
  cout<<'\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 Incorrect 0 ms 344 KB Secret mismatch (possible tampering with the output)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Secret mismatch (possible tampering with the output)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Secret mismatch (possible tampering with the output)
2 Halted 0 ms 0 KB -