제출 #627237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627237		model_code	드문 곤충 (IOI22_insects)	C++17	58.05 / 100	170 ms	460 KiB

insects

// correct/solution-parallel-binser.cpp
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int N) {
  vector <int> colors;
  vector <int> L(N), R(N);
  vector <int> cnt;
  vector <vector<int>> mid;
  
  int rest = 0;
  for (int i = 0; i < N; i++) {
    move_inside(i);
    if (press_button() == 1) {
      R[i] = L[i] = colors.size();
      colors.push_back(i);
      cnt.push_back(1);
      mid.push_back(vector<int>(0));
    }
    else {
      L[i] = 0;
      R[i] = (int)colors.size() - 1;
      move_outside(i);
      mid[(L[i] + R[i]) / 2].push_back(i);
      rest++;
    }
  }
  
  while (rest > 0) {
    for (int i = 0; i < (int)colors.size(); i++) {
      move_outside(colors[i]);
      for (int x : mid[i]) {
        move_inside(x);
        if (press_button() == 1) {
          R[x] = i;
        }
        else {
          L[x] = i + 1;
        }
        move_outside(x);
        
        if (L[x] < R[x]) {
          mid[(L[x] + R[x]) / 2].push_back(x);
        }
        else {
          cnt[L[x]]++;
          rest--;
        }
      }
      mid[i].clear();
    }
    
    for (int i = 0; i < (int)colors.size(); i++) {
      move_inside(colors[i]);
      for (int x : mid[i]) {
        move_inside(x);
        if (press_button() == 2) {
          R[x] = i;
        }
        else {
          L[x] = i + 1;
        }
        move_outside(x);
        
        if (L[x] < R[x]) {
          mid[(L[x] + R[x]) / 2].push_back(x);
        }
        else {
          cnt[L[x]]++;
          rest--;
        }
      }
      mid[i].clear();
    }
  }
  
  int ans = N;
  for (int x : cnt) {
    ans = min(ans,x);
  }
  return ans;
}

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