제출 #1024471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024471		vjudge1	Rarest Insects (IOI22_insects)	C++17	47.98 / 100	174 ms	1112 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> v;
    for(int i=0;i<n;i++){
        move_inside(i);
        if(press_button() != 1){
            move_outside(i);
            int l = 0, r = i - 1, mid = l + r >> 1;
            q.push_back({mid, l, r, i});
        }
        else{
            v.push_back(i);
            is[i] = 1;
            p[i] = i;
        }
    }
    while(v.size()){
        move_outside(v.back());
        v.pop_back();
    }
    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){
                if(is[ptr]){
                    v.push_back(ptr);
                    move_inside(ptr);
                }
                ptr++;
            }
            move_inside(i);
            if(press_button() != 1){
                r = mid - 1;
                p[i] = mid;
            }
            else l = mid + 1;
            move_outside(i);
            if(l <= r){
                int nmid = l + r >> 1;
                nq.push_back({nmid, l, r, i});
            }
        }
        while(v.size()){
            move_outside(v.back());
            v.pop_back();
        }
        q.swap(nq);
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:27:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             int l = 0, r = i - 1, mid = l + r >> 1;
      |                                         ~~^~~
insects.cpp:63:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |                 int nmid = l + r >> 1;
      |                            ~~^~~

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