제출 #1239760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239760		AlperenT_	드문 곤충 (IOI22_insects)	C++20	47.50 / 100	60 ms	436 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 ch(int x){
  vector <int> vec; 
  rep(i , 0 , n-1){
    move_inside(i) ;
    if(press_button() == x+1){
      move_outside(i) ;
    }else{
      vec.pb(i);
    }
  }
  for(int x : vec)move_outside(x); 
  if(sz(vec)==1ll*x*ted)return 1;
  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)move_outside(x) ;
  int l =0 , r = n + 2;
  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: 22.5 / 75