Submission #627611

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627611	2022-08-12T17:37:07 Z	Tigerpants	Rarest Insects (IOI22_insects)	C++17	Compilation error	0 ms	0 KB

insects

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <random>

using namespace std;

typedef vector<int> vi;
typedef set<int> si;
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<bool> vb;

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
    vi x(N);
    for (int i = 0; i < N; i++) {
        x[i] = i;
    }
    shuffle(x.begin(), x.end());

    vb roots(N, false);
    vb inside(N, false);
    vb permanent(N, false);

    int no_roots = 1;
    roots[0] = true;
    move_inside(x[0]);
    inside[0] = true;
    permanent[0] = true;

    for (int i = 1; i < N; i++) {
        move_inside(x[i]);
        inside[i] = true;
        if (press_button() == 2) {
            move_outside(x[i]);
            inside[i] = false;
        } else {
            roots[i] = true;
            permanent[i] = true;
            no_roots++;
        }
    }

    vb active(N, true); // remove those which are too big
    
    if (no_roots == 1) {
        return N;
    }

    int no_inside = no_roots;
    
    int high = (N / no_roots) + 1;
    int low = 1;
    while (low + 1 < high) {
        int middle = (low + high) / 2;
        for (int i = 0; i < N; i++) {
            if ((!inside[i]) && (active[i])) {
                move_inside(x[i]);
                inside[i] = true;
                no_inside++;
                if (press_button() > middle) {
                    move_outside(x[i]);
                    inside[i] = false;
                    no_inside--;
                }
            }
        }
        if (no_inside == middle * no_roots) {
            low = middle;
            // don't remove them. make them permanent
            for (int i = 0; i < N; i++) {
                if (inside[i]) {
                    permanent[i] = true;
                }
            }
        } else {
            high = middle;
            // deactivate all higher ones
            // remove all non-permanent ones
            for (int i = 0; i < N; i++) {
                if (!inside[i]) {
                    active[i] = false;
                } else if (!permanent[i]) {
                    move_outside(x[i]);
                    no_inside--;
                    inside[i] = false;
                }
            }
        }
    }

    return low;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:26:31: error: no matching function for call to 'shuffle(std::vector<int>::iterator, std::vector<int>::iterator)'
   26 |     shuffle(x.begin(), x.end());
      |                               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from insects.cpp:5:
/usr/include/c++/10/bits/stl_algo.h:3748:5: note: candidate: 'template<class _RAIter, class _UGenerator> void std::shuffle(_RAIter, _RAIter, _UGenerator&&)'
 3748 |     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3748:5: note:   template argument deduction/substitution failed:
insects.cpp:26:31: note:   candidate expects 3 arguments, 2 provided
   26 |     shuffle(x.begin(), x.end());
      |                               ^