Submission #1024476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024476		vjudge1	Rarest Insects (IOI22_insects)	C++17	50.30 / 100	106 ms	1256 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;

struct Q{
    int mid, l, r, i;
};

int cnt[maxn];
bool is[maxn];
int p[maxn];

int min_cardinality(int n){
    vector<Q> q;
    vector<int> u;
    for(int i=0;i<n;i++){
        move_inside(i);
        if(press_button() != 1){
            move_outside(i);
            int l = 0, r = (int)u.size() - 1, mid = l + r >> 1;
            q.push_back({mid, l, r, i});
        }
        else{
            u.push_back(i);
            is[i] = 1;
            p[i] = i;
        }
    }
    for(int i=0;i<u.size();i++){
        move_outside(u[i]);
    }
    while(q.size()){
        vector<Q> nq;
        sort(q.begin(), q.end(), [](Q x, Q y){
            return x.mid < y.mid;
        });
        int ptr = 0;
        vector<int> v;
        for(auto [mid, l, r, i]:q){
            while(ptr <= mid){
                v.push_back(u[ptr]);
                move_inside(u[ptr]);
                ptr++;
            }
            move_inside(i);
            if(press_button() != 1){
                r = mid - 1;
                p[i] = u[mid];
            }
            else l = mid + 1;
            move_outside(i);
            if(l <= r){
                int nmid = l + r >> 1;
                nq.push_back({nmid, l, r, i});
            }
        }
        q.swap(nq);
        if(q.size()){
            while(v.size()){
                move_outside(v.back());
                v.pop_back();
            }
        }
    }
    for(int i=0;i<n;i++){
        cnt[p[i]]++;
    }
    int ans = 1e9;
    for(int i=0;i<n;i++){
        if(p[i] == i){
            ans = min(ans, cnt[i]);
        }
    }
    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:27:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             int l = 0, r = (int)u.size() - 1, mid = l + r >> 1;
      |                                                     ~~^~~
insects.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<u.size();i++){
      |                 ~^~~~~~~~~
insects.cpp:60:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |                 int nmid = l + r >> 1;
      |                            ~~^~~

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