oj.uz

Submission #1058266

# Submission time Handle Problem Language Result Execution time Memory
1058266 2024-08-14T09:09:27 Z epicci23 Rarest Insects (IOI22_insects) C++17
0 / 100
 33 ms 476 KB 
#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){
  if(sz(cand)==0) return 999999;
  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;	
  if(sz(cand)==0) return ans;
  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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 448 KB Output is correct
9 Incorrect 2 ms 448 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 448 KB Output is correct
9 Incorrect 2 ms 448 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 444 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 33 ms 464 KB Output is correct
10 Incorrect 20 ms 476 KB Wrong answer.
11 Halted 0 ms 0 KB -