oj.uz

Submission #1058439

# Submission time Handle Problem Language Result Execution time Memory
1058439 2024-08-14T09:59:47 Z epicci23 Rarest Insects (IOI22_insects) C++17
0 / 100
 58 ms 976 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;
void clear_mach(){
  while(!mach.empty()){
  	move_outside(mach.back());
  	mach.pop_back();
  }
}

int solve(vector<int> cand){
   if(sz(cand)==1) return 1;
   mach.push_back(0);
   move_inside(0);
   vector<int> tk,hm;
   tk.push_back(0);
   for(int i=1;i<sz(cand);i++){
   	 move_inside(i);
   	 mach.push_back(i);
   	 if(press_button()==1) tk.push_back(i);
   	 else{
   	 	hm.push_back(i);
   	 	move_outside(i);
   	 	mach.pop_back();
   	 }
   } 
   int n=sz(tk),m=sz(hm);
   if(n==1) return sz(cand);
   if(m<n) return 1;
   int L[m],R[m];
   for(int i=0;i<m;i++){
   	L[i]=0;
   	R[i]=n-1;
   }
   for(int j=0;j<__lg(n);j++){
   	 clear_mach();
   	 vector<int> dene[n];
   	 for(int i=0;i<m;i++) if(L[i]!=R[i]) dene[(L[i]+R[i])/2].push_back(i);
   	 for(int i=0;i<n;i++){
       move_inside(tk[i]);
       mach.push_back(tk[i]);
       for(int x:dene[i]){
       	 move_inside(hm[x]);
       	 mach.push_back(hm[x]);
       	 if(press_button()==2) R[x]=i;
       	 else L[x]=i+1;
       	 move_outside(hm[x]);
       	 mach.pop_back();
       }
   	 }
   }

   int ans=sz(cand);
   vector<int> mark(n,1);
   for(int i=0;i<m;i++) mark[L[i]]++;
   for(int i=0;i<n;i++) ans=min(ans,mark[i]);
   return ans;
}


int min_cardinality(int n){
   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 1 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 Incorrect 5 ms 344 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 5 ms 344 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
7 Correct 7 ms 452 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Incorrect 58 ms 976 KB Wrong answer.
10 Halted 0 ms 0 KB -