제출 #1266561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266561		scalifrastico_098	드문 곤충 (IOI22_insects)	C++20	50.03 / 100	54 ms	420 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int m, op=0, c=0, pk=0; vector<bool> fg;
bool f1(int n)
{
  vector<int> ind; int i=pk, lk=0;
  while(lk<n&&c<op*m)
  {
    if(!fg[i]){ move_inside(i); if(press_button()<=m){fg[i]=true; c++; ind.push_back(i);} else move_outside(i);}
    i++; if(i==n) i=0; lk++;
  } 
  pk=i; if(c==op*m) return true;
  for(auto x:ind){move_outside(x); fg[x]=false; c--;} return false;
} 
int min_cardinality(int n) { 
  op=0; c=0; pk=0; fg.assign(n, false); for(int i=0; i<n; i++){move_inside(i); if(press_button()>1) move_outside(i); else {fg[i]=true; c++; op++;}}
  if(op<=1) return n; if(op==n) return 1;
  int l=1, r=n/op, st=1; while(l+st<=r){st<<=1;} st>>=1;
  while(st>0)
  {
    m=(l+st);if(f1(n)){l+=st;} st>>=1;
  } 
  return l;
}

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