제출 #1124205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124205		epicci23	드문 곤충 (IOI22_insects)	C++17	70 / 100	50 ms	512 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
using namespace std;

vector<int> v;
int D;

inline void Add(int x){
  v.push_back(x);
  move_inside(x);
}

inline void Rem(int x){
  v.pop_back();
  move_outside(x);
}

inline void Clear(){
  while(!v.empty()){
    move_outside(v.back());
    v.pop_back();
  }
}

inline int Get(){
  return press_button();
}

int min_cardinality(int n){
  for(int i=0;i<n;i++){
    Add(i);
    if(Get() == 1) continue;
    Rem(i);
  }

  D = v.size();
  if(D > n / 2) return 1;
  if(D == 1) return n;
  
  if(D <= 45){
    vector<int> lead,vis(n,0),freq(D,1),L(n,0),R(n,D-1);

    for(int x:v){
      vis[x]=1;
      lead.push_back(x);
    }

    for(int Q=0;Q<6;Q++){
      vector<int> ask[n];
      for(int i=0;i<n;i++){
        if(L[i] == R[i] || vis[i]) continue;
        int mid = (L[i]+R[i])/2;
        ask[mid].push_back(i);
      }
      Clear();
      for(int i=0;i<D;i++){
        Add(lead[i]);
        for(int x:ask[i]){
          Add(x);
          if(Get() == 2) R[x] = i;
          else L[x] = i + 1;
          Rem(x);
        }
      }
    } 

    for(int i=0;i<n;i++){
      if(vis[i]) continue;
      freq[L[i]]++; 
    }

    return *min_element(freq.begin(),freq.end());
  }

  int l = 1 , r = n / D;
  while(l < r){
    int B = (l + r + 1) / 2;
    Clear();
    for(int i=0;i<n;i++){
      Add(i);
      if(Get() > B){
        Rem(i);
      }
    }
    if(v.size() == B * D) l = B;
    else r = B - 1;
  }

  return l;
}

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