제출 #1272452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272452		jump	드문 곤충 (IOI22_insects)	C++20	0 / 100	1 ms	332 KiB

insects

void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N);

#include <iostream>
#include <vector>
#include <set>
bool markMax[2010];
bool markMin[2010];
int type[2010];
std::set<int> clearList;
int ct = 1;
int markcnt = 0;
int recentmin = 2000;
int recentmax = 2000;
int size;
int pbv = 0;
int clear(){
  for(auto c:clearList){
    move_outside(c);
  }
  return 0;
}
int maxL(){
  //this cost atmost 2*N,2*N,2*N including clear
  //assuming empty
  //return the max cardinallity as well as marking them
  int count=1;
  int last = 0;
  int nw = -1;
  for(int i=0;i<size;i++){
    if(markMax[i]||markMin[i])continue;
    move_inside(i);
    pbv = press_button();
    if(pbv>last){
      nw = i;
    }
    last = pbv;
  }
  if(nw==-1)return 0;
  type[nw]=ct++;
  markMax[nw]=true;
  last = pbv;
  for(int i=0;i<size;i++){
    if(markMax[i]||markMin[i])continue;
    move_outside(i);
    pbv = press_button();
    if(pbv<last){
      markMax[i]=true;
      count+=1;
      type[i]=type[nw];
      move_inside(i);
      clearList.insert(i);
    }
  }
  clear();
  return count;
}
int minL(){
  //this cost atmost N,N,N including clear
  //assuming empty
  //return amount of type of insect as well as marking non-duplicate
  int count = 0;
  for(int i=0;i<size;i++){
    if(markMax[i]||markMin[i])continue;
    move_inside(i);
    pbv = press_button();
    if(pbv>1){
      move_outside(i);
    }
    else{
      count+=1;
      markMin[i]=true;
      clearList.insert(i);
    }
  }
  clear();
  return count;
}

int min_cardinality(int N) {
  size=N;
  int lastC=0;
  int lastG=0;
  int q=0;
  int mlc = 0;
  while(q++<10000){
    int gs1 = maxL();if(gs1!=0)lastC-=1;
    int ds1 = minL();mlc+=1;

    for(int i=0;i<N;i++){
      //std::cout << '(' << markMax[i] << ',' << markMin[i] << ')';
    }
    //std::cout << gs1 << ' ' << ds1 << '\n';

    if(gs1==1){
      return mlc;
    }
    if(lastC>ds1&&lastC!=-1){
      return mlc-1;
    }
    lastC=ds1;
    lastG=gs1;
  }
  return 0;
}

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