Submission #804558

#	Time	Username	Problem	Language	Result	Execution time	Memory
804558		Ronin13	Rarest Insects (IOI22_insects)	C++17	0 / 100	115 ms	336 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back 
using namespace std;

int min_cardinality(int n) {
  vector <int> act;
  bool used[n + 1];
  fill(used, used + n + 1, false);
  for(int i = 0; i < n; i++){
    move_inside(i);
    int x = press_button();
    if(x == 2) move_outside(i), used[i] = true;
    else act.pb(i);
  }
  //for(int to : act) cout << to << ' ';
  //int l = 0, r = act.size();
  for(int to : act) move_outside(to);
  int L[n], R[n];
  for(int i = 0; i < n; i++){
    if(used[i]) L[i] = -1, R[i] =act.size()- 1;
  }
  for(int j = 0; j < 12; j++){
    vector <vector <int> > vv(act.size());
    for(int i = 0; i < n; i++){
      if(L[i] - R[i] == -1) continue;
      if(!used[i]) continue;
      int mid = L[i] + R[i];
      
      mid /= 2;
     // cout << mid << "\n";
      vv[mid].pb(i);
    }
    bool ind = false;
    for(int i = 0; i < act.size(); i++){
      if(!vv[i].empty()) ind = true;
    }
    if(!ind) break;
    for(int i= 0; i < act.size(); i++){
      move_inside(act[i]);
      for(int to : vv[i]){
        move_inside(to);
        int x = press_button();
        if(x == 2) R[to] = i;
        else L[to] = i;
        move_outside(to);
      }
      for(int to : act) move_outside(to);
    }
  }
  int cnt[n + 1];
  fill(cnt, cnt + n + 1, 1e9);
  
  for(int j = 0; j < act.size(); j++){
    cnt[j] = 1;
  }
  for(int i = 0; i < n; i++){
    if(used[i]) cnt[R[i]]++;
  }
  int mn = 1e9;
  for(int i = 0; i < act.size(); i++){
      mn = min(mn, cnt[i]);
  }
  return mn;
  return 0;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < act.size(); i++){
      |                    ~~^~~~~~~~~~~~
insects.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i= 0; i < act.size(); i++){
      |                   ~~^~~~~~~~~~~~
insects.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int j = 0; j < act.size(); j++){
      |                  ~~^~~~~~~~~~~~
insects.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int i = 0; i < act.size(); i++){
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75