Submission #3772602

---

Source Code Expand

#include <vector>

using namespace std;

using u8 = unsigned char;
using uint = unsigned int;

class bitVector {
public:
    uint length, cnum, bnum;
    // bit列の長さ、chunk数、chunk毎のblock数

    static int cw, bw;
    // chunkの幅、blockの幅 今回は256, 64

    vector<uint> bit;
    vector<uint> chunk;
    vector<vector<u8>> blocks;


    explicit bitVector(uint N) : length(N) {
        cnum = (length + cw - 1) / cw;
        // length / cwを切り上げたものが必要なchunkの個数
        bnum = cw / bw;

        bit.assign(cnum * bnum, 0);
        chunk.assign(cnum + 1, 0);
        // +1は先頭の0が入っているやつの分
        blocks.assign(cnum, vector<u8>(bnum + 1, 0));
        // こっちの+1も同じく
    }

    // pos桁目をbに変える
    void set(int pos, int b) {
        int bpos = pos / bw;
        // bit内でposが存在するblockの番号
        int offset = pos % bw;
        // そのblock内でのposのindex

        if (b == 0) {
            bit[bpos] &= ~(1 << offset);
        } else if (b == 1) {
            bit[bpos] |= (1 << offset);
        }
    }

    // pos桁目のbitを返す
    int access(int pos) const {
        assert(pos < length);

        int bpos = pos / bw;
        int offset = pos % bw;
        return bit[bpos] >> offset & 1;
    }

    uint popCount(uint num) const {
        // __builtin_popcountが使えなければ黒魔術
        return __builtin_popcount(num);
    }

    // chunkとblocksを適切に埋める
    void build() {
        chunk[0] = 0;
        for (int i = 0; i < cnum; ++i) {
            blocks[i][0] = 0;
            for (int j = 0; j < bnum; ++j) {
                blocks[i][j + 1] = blocks[i][j] + popCount(bit[i * bnum + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bnum];
        }
    }

    // [0, pos)にあるkindの数を返す
    int rank(int pos, int kind) const {
        assert(kind <= 1);
        if (kind == 0) {
            return pos - rank1(pos);
        } else {
            return rank1(pos);
        }
    }

    // [0, pos)にある1の数を返す
    int rank1(int pos) const {
        int cpos = pos / cw;
        int bpos = pos % cw / bw;
        int offset = pos % bw;

        uint masked = (bit[cpos * bnum + bpos]) & ((1 << offset) - 1);
        return chunk[cpos] + blocks[cpos][bpos] + popCount(masked);
    }

    // rank(idx, kind)=numなる最小のidxを返す
    // そもそもkindがnum個なかったら-1を返す
    int select(int num, int kind) const {
        if (num == 0) return 0;
        if (rank(length, kind) < num) return -1;

        int ok = length, ng = 0;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (rank(mid, kind) >= num) {
                ok = num;
            } else {
                ng = num;
            }
        }

        return ok;
    }
};

int bitVector::cw = 256;
int bitVector::bw = 32;


#include <iostream>
#include <string>

int main() {
    int N;
    string S;
    cin >> N >> S;

    bitVector bv(N);

    for (int i = 0; i < N; ++i) {
        bv.set(i, S[i] == 'W' ? 1 : 0);
    }

    int ans = N;
    for (int i = 1; i <= N; ++i) {
        ans = min(ans, bv.rank(i - 1, 1) + (bv.rank(N, 0) - bv.rank(i, 0)));
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function ‘int bitVector::access(int) const’:
./Main.cpp:49:28: error: ‘assert’ was not declared in this scope
         assert(pos < length);
                            ^
./Main.cpp: In member function ‘int bitVector::rank(int, int) const’:
./Main.cpp:75:25: error: ‘assert’ was not declared in this scope
         assert(kind <= 1);
                         ^