Submission #1025198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025198		Wansur	Rarest Insects (IOI22_insects)	C++17	100 / 100	48 ms	944 KiB

insects

#include <bits/stdc++.h>
#define ent '\n'

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

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 12;

mt19937 rng(10223431);
bool used[maxn];
vector<int> p, d, a, b;
int n, m, c, cnt;

bool check(int x){
    x -= cnt;
    for(int x:a){
        move_outside(x);
    }
    a.clear();
    b.clear();
    for(int i:p){
        if(used[i]) continue;
        move_inside(i);
        if(press_button() > x){
            move_outside(i);
            b.push_back(i);
        }
        else a.push_back(i);
        if(a.size() == x * m) break;
    }
    if(a.size() == x * m){
        cnt += x;
        for(int x:a){
            used[x] = 1;
            c--;
        }
        return 1;
    }
    for(int x:b){
        used[x] = 1;
        c--;
    }
    return 0;
}

int min_cardinality(int N){
    n = N;
    c = n;
    for(int i=0;i<n;i++){
        p.push_back(i);
        move_inside(i);
        if(press_button() != 1){
            move_outside(i);
        }
        else m++;
    }
    for(int i=0;i<n;i++){
        swap(p[i], p[rng() % n]);
    }
    int ans = 0;
    for(int l = 1, r = n / m; l <= r;){
        int mid = l + r >> 1;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'bool check(int)':
insects.cpp:32:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if(a.size() == x * m) break;
      |            ~~~~~~~~~^~~~~~~~
insects.cpp:34:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(a.size() == x * m){
      |        ~~~~~~~~~^~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = l + r >> 1;
      |                   ~~^~~

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