Submission #1240593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240593		AlperenT_	Rarest Insects (IOI22_insects)	C++20	98.74 / 100	15 ms	440 KiB

insects

#include "insects.h"
#include <bits/stdc++.h> 
//#include "segments.h"
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 5000 + 10 , inf = 1e9+ 10 , mod = 998244353;
int ted= 0 , n;
int mark[maxn]  ;
int ch(int x){
  vector <int> vec , vec2 ; 
  int fix =0 ; 
  rep(i , 0 , n-1){
    if(mark[i] == 2)continue ;
    if(mark[i] == 1){fix ++ ; continue ;} 
    move_inside(i) ;
    if(press_button() == x+1){
      move_outside(i) ;
      vec2.pb(i); 
    }else{
      vec.pb(i);
    }
  }
  if(sz(vec)+fix==1ll*x*ted){
    for(int x : vec)mark[x] = 1 ;
    return 1;
  }
  for(int x : vec) move_outside(x); 
  for(int x : vec2)mark[x] =2 ;
  return 0 ;
}


int min_cardinality(int N){
   n = N ; 
  vector <int> vec; 
  rep(i ,0, n-1){
    move_inside(i) ;
    if(press_button() == 2){
      move_outside(i);
    }else{
      vec.pb(i);
      ted++;
    }
  }
  for(int x : vec)mark[x] = 1 ;
  if(ted==1)return n ;
  int l =0 , r = n/ted + 5;
  while(r-l > 1){
    int m = (l+r)/2 ;
    if(ch(m) == 1){
      l = m ;
    }else{
      r = m ;
    }
  }
  return l ; 
}

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