Submission #878577

#	Time	Username	Problem	Language	Result	Execution time	Memory
878577		Clan328	Rarest Insects (IOI22_insects)	C++17	42.69 / 100	141 ms	1644 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
  for (auto elem : v) 
    stream << elem << " ";
  return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
    stream >> elem;
   return stream;
}

vi first;

bool check(int N, int rarity) {
  vi inside, outside;

  for (int i = 0; i < N; i++) {
    move_inside(i);
    if (i >= rarity && press_button() > rarity) {
      move_outside(i);
      outside.pb(i);
    } else {
      inside.pb(i);
    }
  }

  for (int i = 0; i < inside.size(); i++) move_outside(inside[i]);

  if (inside.size() % rarity != 0) return true;
  if (inside.size()/rarity > outside.size()) return true;

  // if (rarity == 1) {
  //   cout << outside << nL;
  // }

  vi outside2;
  for (int i = 0; i < outside.size(); i++) {
    move_inside(outside[i]);
    if (press_button() == 1) {
      outside2.pb(outside[i]);
    } else {
      move_outside(outside[i]);
    }
  }

  // if (rarity == 6) {
  //   cout << outside2 << nL;
  // }

  bool res = false;
  int curr = press_button();
  for (int i = 0; i < first.size() && !res; i++) {
    move_inside(first[i]);
    if (press_button() == curr) {
      res = true;
    }
    move_outside(first[i]);
  }

  for (int i = 0; i < outside2.size(); i++) move_outside(outside2[i]);

  return res;
}

int min_cardinality(int N) {
  first = vi();
  for (int i = 0; i < N; i++) {
    move_inside(i);
    if (press_button() == 1) {
      first.pb(i);
    } else {
      move_outside(i);
    }
  }
  for (int i = 0; i < first.size(); i++) move_outside(first[i]);

  if (first.size() > N/2) return 1;

  int maxN = (N-first.size())+1;
  int lo = 1, hi = maxN-1, res = maxN, mid;
  while (lo <= hi) {
    mid = (lo+hi)/2;
    if (check(N, mid)) {
      res = mid;
      hi = mid - 1;
    } else
      lo = mid + 1;
  }

  return res;
}

Compilation message (stderr)

insects.cpp: In function 'bool check(int, int)':
insects.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i = 0; i < inside.size(); i++) move_outside(inside[i]);
      |                   ~~^~~~~~~~~~~~~~~
insects.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i = 0; i < outside.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
insects.cpp:88:21: 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 < first.size() && !res; i++) {
      |                   ~~^~~~~~~~~~~~~~
insects.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (int i = 0; i < outside2.size(); i++) move_outside(outside2[i]);
      |                   ~~^~~~~~~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (int i = 0; i < first.size(); i++) move_outside(first[i]);
      |                   ~~^~~~~~~~~~~~~~
insects.cpp:113:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |   if (first.size() > N/2) return 1;
      |       ~~~~~~~~~~~~~^~~~~

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