제출 #1065237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065237		cjoa	드문 곤충 (IOI22_insects)	C++17	99.95 / 100	51 ms	688 KiB

insects

#include "insects.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>

using namespace std;

enum State {
   OUTSIDE, INSIDE, DISCARDED
};

int N, T;
int cnt_inside;
vector<int> state;

void MOVE_IN(int n) {
// cerr << "+ " << n << endl;
   assert(state[n] == OUTSIDE);
   move_inside(n);
   state[n] = INSIDE;
   ++cnt_inside;
}

void MOVE_OUT(int n) {
// cerr << "- " << n << endl;
   assert(state[n] == INSIDE);
   move_outside(n);
   state[n] = OUTSIDE;
   --cnt_inside;
}

bool check(int x) {
   for (int n = 0; n < N and cnt_inside < T * x; ++n) {
      if (state[n] != OUTSIDE)
         continue;
      MOVE_IN(n);
      int f = press_button();
      if (f > x)
         MOVE_OUT(n);
   }

   return cnt_inside == T * x;
}

void RESTORE(const vector<int>& orig_state) {
   for (int n = 0; n < N; ++n) {
      if (state[n] != orig_state[n]) {
         assert(orig_state[n] == OUTSIDE);
         MOVE_OUT(n);
      }
      else if (state[n] == OUTSIDE) {
         state[n] = DISCARDED;
      }
   }
}

int min_cardinality(int _N) {
   N = _N;
   T = _N;
   cnt_inside = 0;
   state.assign(N, OUTSIDE);
   check(1);
   T = cnt_inside;

   int res = 1;
   int lo = 2, hi = N / T;
   while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      vector<int> orig_state = state;
      if (check(mid)) {
         lo = mid+1;
         res = mid;
      }
      else {
         hi = mid-1;
         RESTORE(orig_state);
      }
   }

   return res;
}

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