verify/verify-yosupo-ds/yosupo-bitset.test.cpp

• View this file on GitHub
• Last update: 2025-03-29 17:57:48+08:00
• Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/dynamic-bitset.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/predecessor_problem

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/dynamic-bitset.hpp"
#include <iostream>

std::string T;
int n, q, opt, x;

int main(int argc, char const *argv[]) {
    optimizeIO();
    std::cin >> n >> q >> T;

    DynamicBitset bit(n);

    for (int i = 0; i < n; i++) {
        if (T[i] == '1') bit.set(i);
    }

    while (q--) {
        std::cin >> opt >> x;
        if (opt == 0) {
            bit.set(x);
        } else if (opt == 1) {
            bit.set(x, false);
        } else if (opt == 2) {
            std::cout << bit.test(x) << '\n';
        } else if (opt == 3) {
            std::cout << bit.suf(x, true) << '\n';
        } else {
            std::cout << bit.pre(x, true) << '\n';
        }
    }

    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-bitset.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/predecessor_problem

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/dynamic-bitset.hpp"



#line 7 "src/alfred/data_structure/dynamic-bitset.hpp"

// TODO: Implement resize and bitwise operators. Figure out how to mod.

class DynamicBitset {
private:
    using Word_t = unsigned long long;
    constexpr static int bw = sizeof(Word_t) * 8;
    constexpr static Word_t WORD_MAX = std::numeric_limits<Word_t>::max();
    size_t n, cnt;
    std::vector<Word_t> bits;

    inline int calc_len(void) {
        return (std::max<size_t>(n, bw) + bw - 1) / bw;
    }

public:
    DynamicBitset(size_t N) : n(N), bits(calc_len()) {}
    inline int size(void) { return n; }
    inline int count(void) { return cnt; }
    inline int test(size_t i) { return (bits[i / bw] >> (i % bw)) & 1; }
    inline void set(size_t i, bool val = true) {
        if (test(i) == val) return;
        bits[i / bw] ^= (1ULL << (i % bw));
        val ? cnt++ : cnt--;
    }
    inline void flip(size_t i) {
        bits[i / bw] ^= (1ULL << (i % bw));
        test(i) ? cnt-- : cnt++;
    }
    inline void reset(void) {
        std::fill(bits.begin(), bits.end(), 0);
        cnt = 0;
    }
    inline void clear(void) {
        bits.clear(), cnt = n = 0;
    }
    // find the previous val before i. returns -1 if not found.
    inline int pre(size_t i, bool contain = false, bool val = true) {
        Word_t cur = bits[i / bw];
        for (int j = (int)(i % bw) - (!contain); j >= 0; j--) {
            if ((cur >> j & 1) == val) {
                return i - (i % bw - j);
            }
        }
        for (int j = i / bw - 1; j >= 0; j--) {
            if (bits[j] == (val ? 0 : WORD_MAX)) continue;
            for (int k = bw - 1; k >= 0; k--) {
                if ((bits[j] >> k & 1) == val) {
                    return j * bw + k;
                }
            }
        }
        return -1;
    }
    inline int suf(size_t i, bool contain = false, bool val = true) {
        Word_t cur = bits[i / bw];
        for (int j = i % bw + (!contain); j < bw; j++) {
            if ((cur >> j & 1) == val) {
                return i + (j - i % bw);
            }
        }
        const int len = calc_len();
        for (int j = i / bw + 1; j < len; j++) {
            if (bits[j] == (val ? 0 : WORD_MAX)) continue;
            for (int k = 0; k < bw; k++) {
                if ((bits[j] >> k & 1) == val) {
                    return j * bw + k;
                }
            }
        }
        return -1;
    }
};


#line 6 "verify/verify-yosupo-ds/yosupo-bitset.test.cpp"

std::string T;
int n, q, opt, x;

int main(int argc, char const *argv[]) {
    optimizeIO();
    std::cin >> n >> q >> T;

    DynamicBitset bit(n);

    for (int i = 0; i < n; i++) {
        if (T[i] == '1') bit.set(i);
    }

    while (q--) {
        std::cin >> opt >> x;
        if (opt == 0) {
            bit.set(x);
        } else if (opt == 1) {
            bit.set(x, false);
        } else if (opt == 2) {
            std::cout << bit.test(x) << '\n';
        } else if (opt == 3) {
            std::cout << bit.suf(x, true) << '\n';
        } else {
            std::cout << bit.pre(x, true) << '\n';
        }
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	hack_00	AC	6 ms	4 MB
g++	max_all0_00	AC	41168 ms	20 MB
g++	max_all0_01	AC	41067 ms	20 MB
g++	max_all1_00	AC	169 ms	20 MB
g++	max_all1_01	AC	169 ms	20 MB
g++	max_query0_1_2_00	AC	178 ms	20 MB
g++	max_query0_1_2_01	AC	177 ms	20 MB
g++	max_random_00	AC	198 ms	20 MB
g++	max_random_01	AC	193 ms	20 MB
g++	max_sparse_00	AC	11924 ms	20 MB
g++	max_sparse_01	AC	11858 ms	20 MB
g++	medium_00	AC	18 ms	4 MB
g++	medium_01	AC	17 ms	4 MB
g++	medium_02	AC	17 ms	4 MB
g++	medium_03	AC	17 ms	4 MB
g++	medium_04	AC	16 ms	4 MB
g++	small_00	AC	16 ms	4 MB
g++	small_01	AC	16 ms	4 MB
g++	small_02	AC	16 ms	4 MB
g++	small_03	AC	16 ms	4 MB
g++	small_04	AC	16 ms	4 MB

Back to top page