Submission #1239742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239742		AlperenT_	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	408 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;

pair <int , vector <int> > solve(int l , int r ){
  if(l == r){
    pair<int,vector <int> > vec ;
    vec.F = 1 ;
    vec.S.pb(l) ;
    move_inside(l) ;
    return vec; 
  }
  pair<int,vector <int> > ans; 
  int mid = (l+r)/2 ;
  pair <int , vector <int> > a = solve(l , mid) ;
  for(int x : a.S)move_outside(x);
  pair <int , vector <int> > b = solve(mid+1 , r) ;
  vector <int> vec , vec2 ;
  if(a.F == b.F){
    for(int x :a.S){
      move_inside(x);
      if(press_button()==2){
        vec.pb(x);
        move_outside(x);
      }else{
        vec2.pb(x);
      }
    }
    if(sz(vec) == sz(a.S) && sz(a.S )== sz(b.S)){
      ans.F = a.F*2 ;
      ans.S = b.S ;
      return ans ;
    }
    ans.F = a.F ;
    ans.S = vec2 ;
    for(int x : vec)move_inside(x) ;
    for(int x : b.S)move_outside(x);
    for(int x : b.S){
      move_inside(x);
      if(press_button() == 2){
        move_outside(x);
      }else{
        ans.S.pb(x); 
      }
    }
    for(int x : vec)move_outside(x) ;
    return ans ;
  }else{
    for(int x : b.S)move_outside(x) ;
    if(a.F > b.F)swap(a,b) ;
    for(int x : b.S)move_inside(x) ;
    for(int x :a.S){
      move_inside(x);
      if(press_button() == 2){
        move_outside(x);
        vec.pb(x);
      }else{
        vec2.pb(x);
      }
    }
    if(sz(vec)== sz(a.S)){
      if(sz(vec) == sz(b.S)){
        ans.F = a.F + b.F ;
        ans.S = b.S;
        return ans ;
      }
      for(int x : a.S)move_inside(x);
      for(int x : b.S)move_outside(x) ;
      ans.F = b.F; 
      for(int x : b.S){
        move_inside(x);
        if(press_button() == 2){
            move_outside(x);
        }else{
          ans.S.pb(x);
        }
      }
      for(int x : a.S)move_outside(x); 
      return ans ;
    }else{
      for(int x : b.S)move_outside(x) ;
      ans.F = a.F ; 
      ans.S = vec2 ;
      return ans ;
    }
  }
}


int min_cardinality(int n){
  pair<int,vector <int> > vec = solve(0 , n-1) ;
  return vec.F ; 
}

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