Submission #711165

#	Time	Username	Problem	Language	Result	Execution time	Memory
711165		PoonYaPat	Rarest Insects (IOI22_insects)	C++17	100 / 100	57 ms	412 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
 
queue<int> out,in,temp,temp2;
int type;
 
int min_cardinality(int n) {
    for (int i=0; i<n; ++i) {
        move_inside(i);
        if (press_button()>1) move_outside(i), out.push(i);
        else ++type, in.push(i);
    }
 
    int l=1,r=n/type;
    int cnt=0;
    while (l<r) {
        int mid=(l+r+1)/2;
        //check whether ans is less than mid or not
 
        while (!out.empty()) {
            move_inside(out.front());
 
            if (press_button()>mid) move_outside(out.front()), temp2.push(out.front());
            else temp.push(out.front());
            out.pop();
 
            if (in.size()+temp.size()==type*mid) break;
        }
        while (!temp2.empty()) {
            out.push(temp2.front());
            temp2.pop();
        }
 
        if (in.size()+temp.size()==type*mid) {
            l=mid;
            while (!temp.empty()) {
                in.push(temp.front());
                temp.pop();
            }
        } else {
            r=mid-1;
            while (!out.empty()) out.pop();
            while (!temp.empty()) {
                out.push(temp.front());
                move_outside(temp.front());
                temp.pop();
            }
        }
    }
    return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:28:38: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |             if (in.size()+temp.size()==type*mid) break;
      |                 ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:35:34: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         if (in.size()+temp.size()==type*mid) {
      |             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:16:9: warning: unused variable 'cnt' [-Wunused-variable]
   16 |     int cnt=0;
      |         ^~~

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