Submission #852330

#	Time	Username	Problem	Language	Result	Execution time	Memory
852330		fadi57	Rarest Insects (IOI22_insects)	C++17	47.51 / 100	139 ms	1876 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
int n;
const int mx=2e7+10;
map<int,int>in;
int sz=0;
int d=0;
/*
bool check(int x)
{
  vector<int>removee;
    for(int i=0; i<n; i++)
    {
           if(in[i]){

           }else{
                move_inside(i);
              int z=press_button();
               if(z>x)
                    {
                  move_outside(i);
                   }else{
                     removee.push_back(i);
                   }
           }

       }
    int z=press_button();
   for(auto it:removee){
    move_outside(*it);
   }
    if(removee.size()==d*(x-1))
    {
        return 1;
    }
    else
    {
        return 0;
    }

}*/
int min_cardinality(int N)
{
    int arr[N+1];
    n=N;
    for(int i=0; i<N; i++)
    {
        arr[i]=-1;
    }

vector<int>v;
    for(int i=0; i<N; i++)
    {
        move_inside(i);
        //in[i]=1;
        d++;
        int z=  press_button();
        if(z>1)
        {
            move_outside(i);
            in[i]=0;
            d--;
        }
        else
        {
            v.push_back(i);
            sz++;
        }


    }
    int l=1;
    int r=N;
    int ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        sz=0;
        vector<int> to_remove;
       for (int i = 0; i < N; i++) {
			if (!binary_search(v.begin(), v.end(), i)) {
				move_inside(i);
				if (press_button() > mid) {
					move_outside(i);
				} else {
					to_remove.push_back(i);
				}
			}
		}
		if ((int)to_remove.size() == (int)v.size() * (mid - 1)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
		for (auto i : to_remove) {
			move_outside(i);
		}


    }
    return ans;


}
/*
int main(){
cout<<min_cardinality(9);


}*/

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:45:9: warning: variable 'arr' set but not used [-Wunused-but-set-variable]
   45 |     int arr[N+1];
      |         ^~~

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