제출 #628897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628897		600Mihnea	드문 곤충 (IOI22_insects)	C++17	99.89 / 100	65 ms	552 KiB

insects

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

using namespace std;

set<int> s;
set<int> invalid;

void add(int i) {
  assert(!s.count(i));
  s.insert(i);
  move_inside(i);
}

void del(int i) {
  assert(s.count(i));
  s.erase(i);
  move_outside(i);
}

int get() {
  return press_button();
}

int get_s_cardinality() {
  int sol = 0;
  for (auto &x : s) {
    if (!invalid.count(x)) {
      sol++;
    }
  }
  return sol;
}

int min_cardinality(int n) {
  int cnt_distinct = 0;
  for (int i = 0; i < n; i++) {
    add(i);
    if (get() == 1) {
      cnt_distinct++;
    } else {
      del(i);
    }
  }

  for (auto &i : s) {
    invalid.insert(i);
  }

  int low = 1, high = n, sol = 1;
  while (low <= high) {
    assert(low >= 1);
    {
      int cnt_valid = 0;
      for (int i = 0; i < n; i++) {
        if (invalid.count(i)) continue;
        cnt_valid++;
      }
      high = min(high, cnt_valid / cnt_distinct);
    }

    if (!(low <= high)) break;

    int mid = (low + high) / 2;
    vector<int> added_now, wait_now;
    for (int i = 0; i < n; i++) {
      if (invalid.count(i)) continue;
      add(i);
      if (get() > mid + sol) {
        del(i);
        wait_now.push_back(i);
      } else {
        added_now.push_back(i);
      }
    }
    if (get_s_cardinality() == mid * cnt_distinct) {
      for (auto &i : added_now) {
        invalid.insert(i);
      }
      int delta = mid;
      low = mid + 1;

      sol += delta;
      low -= delta;
      high -= delta;

    } else {
      for (auto &i : added_now) {
        del(i);
      }
      for (auto &i : wait_now) {
        invalid.insert(i);
      }
      high = mid - 1;
    }
  }
  return sol;
}

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