oj.uz

Submission #1024450

# Submission time Handle Problem Language Result Execution time Memory
1024450 2024-07-16T05:23:05 Z vjudge1 Rarest Insects (IOI22_insects) C++17
0 / 100
 9 ms 700 KB 
#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();
    }
    sort(q.begin(), q.end(), [](Q x, Q y){
        return x.mid < y.mid;
    });
    while(q.size()){
        vector<Q> nq;
        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;
}

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 9 ms 700 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Incorrect 8 ms 464 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 9 ms 700 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Incorrect 8 ms 464 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB Wrong answer.
7 Halted 0 ms 0 KB -