Submission #720762

#	Time	Username	Problem	Language	Result	Execution time	Memory
720762		nguyentunglam	Rarest Insects (IOI22_insects)	C++17	57.77 / 100	160 ms	428 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
bool mark[N];
int solve(vector<int> &v1, vector<int> &v2) {
    if (v1.size() == 1) return 1 + v2.size();
    int mid = v1.size() / 2;
    vector<int> tmp1, tmp2, tmp3;
    for(int j = 0; j < mid; j++) tmp1.push_back(v1[j]);
    for(int j = mid; j < v1.size(); j++) move_outside(v1[j]);
    for(int &j : v2) {
        move_inside(j);
        if (press_button() > 1) tmp2.push_back(j);
        else tmp3.push_back(j);
        move_outside(j);
    }
    int ret1 = solve(tmp1, tmp2);
    tmp1.clear(); tmp2.clear();
    for(int j = mid; j < v1.size(); j++) {
        tmp1.push_back(v1[j]);
        move_inside(v1[j]);
    }
    int ret2 = solve(tmp1, tmp3);
    return min(ret1, ret2);
}
int min_cardinality(int n) {
    vector<int> v1, v2;
    for(int i = 0; i < n; i++) {
        move_inside(i);
        if (press_button() > 1) move_outside(i), v2.push_back(i);
        else v1.push_back(i);
    }
    return solve(v1, v2);
}

Compilation message (stderr)

insects.cpp: In function 'int solve(std::vector<int>&, std::vector<int>&)':
insects.cpp:11:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int j = mid; j < v1.size(); j++) move_outside(v1[j]);
      |                      ~~^~~~~~~~~~~
insects.cpp:20:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int j = mid; j < v1.size(); j++) {
      |                      ~~^~~~~~~~~~~

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