Submission #1058220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058220		epicci23	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	344 KiB

insects

#include "bits/stdc++.h"
#include "insects.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;


vector<int> mach;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N;
void clear_mach(){
  while(!mach.empty()){
  	move_outside(mach.back());
  	mach.pop_back();
  }
}


int solve(vector<int> cand){
  clear_mach();
  if(sz(cand)==1) return 1;
  shuffle(all(cand),rng);
  int n=sz(cand);
  move_inside(cand[0]);
  mach.push_back(cand[0]);
  int last=1;
  for(int i=1;i<n;i++){
    move_inside(cand[i]);
    mach.push_back(cand[i]);
    if(last==press_button()){
    	move_outside(cand[i]);
    	mach.pop_back();
    }
    else last++;
  }
  int ans=last;
  if(last==1) return 1;
  vector<int> vis(N,0);
  for(int x:mach) vis[x]=1;
  clear_mach();
  vector<int> cand_new;
  for(int x:cand) if(!vis[x]) cand_new.push_back(x);
  cand=cand_new;
  if(sz(cand)==1) return 1;	
  shuffle(all(cand),mt19937(0));
  vector<int> takla;
  for(int x:cand){
  	move_inside(x);
  	mach.push_back(x);
  	int cur = press_button();
  	if(cur>=last){
  	  move_outside(x);
  	  mach.pop_back();
  	  takla.push_back(x);
  	}
  }
  if(takla.empty()){
    clear_mach();
    return solve(cand);
  }
  clear_mach();
  vector<int> cikar;
  for(int x:takla) cikar.push_back(x);
  move_inside(takla[0]);
  mach.push_back(takla[0]);
  for(int i=1;i<sz(takla);i++){
  	move_inside(takla[i]);
  	mach.push_back(takla[i]);
  	if(press_button()==2){
  	  move_outside(takla[i]);
  	  mach.pop_back();	
  	}
  }
  for(int x:cand){
  	move_inside(x);
  	mach.push_back(x);
  	if(press_button()==2){
  	  move_outside(x);
  	  mach.pop_back();
  	  cikar.push_back(x);
  	}
  }
  vis.assign(N,0);
  for(int x:cikar) vis[x]=1;
  vector<int> newnew;
  for(int x:cand) if(!vis[x]) newnew.push_back(x);
  cand=newnew;
  return min(ans,solve(cand));
}


int min_cardinality(int n){
   N=n+5;
   vector<int> res;
   for(int i=0;i<n;i++) res.push_back(i);
   return solve(res); 
}

/*void _(){
	
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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