Submission #805598

#	Time	Username	Problem	Language	Result	Execution time	Memory
805598		Ronin13	Rarest Insects (IOI22_insects)	C++17	70 / 100	107 ms	420 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);
  if((int)act.size() * (int)act.size() > n){
      int l = 0, r = n / (int)act.size();
      int cnt = 0;
      while(l + 1 < r){
          int mid = (l + r) / 2;
          int cnt = 0;
          vector <int> cur;
          for(int i = n - 1; i >= 0; i--){
            move_inside(i);
            cur.pb(i);
            int x = press_button();
            if(x > mid){
              if(!used[i]) cnt++;
              move_outside(i);cur.pop_back();
            }
          }
          while(!cur.empty()) move_outside(cur.back()), cur.pop_back();
          if(cnt < act.size()) r = mid;
          else l = mid;
      }
      return r;
  }
  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 < 11; 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);
    }
    
    
    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:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |           if(cnt < act.size()) r = mid;
      |              ~~~~^~~~~~~~~~~~
insects.cpp:28:11: warning: unused variable 'cnt' [-Wunused-variable]
   28 |       int cnt = 0;
      |           ^~~
insects.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i= 0; i < act.size(); i++){
      |                   ~~^~~~~~~~~~~~
insects.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int j = 0; j < act.size(); j++){
      |                  ~~^~~~~~~~~~~~
insects.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i = 0; i < act.size(); i++){
      |                  ~~^~~~~~~~~~~~

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