Submission #3772628


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, 32

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


    explicit bitVector(int 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, 0));
    }

    // 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 - 1; ++j) {
                blocks[i][j + 1] = blocks[i][j] + popCount(bit[i * bnum + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bnum - 1] + popCount(bit[(i + 1) * bnum - 1]);
        }
    }

    // [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);
    }

    bv.build();
    int ans = N;

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

Submission Info

Submission Time
Task C - Attention
User Tiramister
Language C++14 (GCC 5.4.1)
Score 300
Code Size 3519 Byte
Status AC
Exec Time 22 ms
Memory 900 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 26
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 19 ms 644 KB
subtask_1_02.txt AC 5 ms 384 KB
subtask_1_03.txt AC 14 ms 640 KB
subtask_1_04.txt AC 13 ms 640 KB
subtask_1_05.txt AC 8 ms 512 KB
subtask_1_06.txt AC 20 ms 900 KB
subtask_1_07.txt AC 20 ms 900 KB
subtask_1_08.txt AC 19 ms 900 KB
subtask_1_09.txt AC 15 ms 644 KB
subtask_1_10.txt AC 22 ms 900 KB
subtask_1_11.txt AC 22 ms 900 KB
subtask_1_12.txt AC 22 ms 900 KB
subtask_1_13.txt AC 21 ms 900 KB
subtask_1_14.txt AC 20 ms 900 KB
subtask_1_15.txt AC 20 ms 900 KB
subtask_1_16.txt AC 20 ms 900 KB
subtask_1_17.txt AC 21 ms 900 KB
subtask_1_18.txt AC 20 ms 900 KB
subtask_1_19.txt AC 20 ms 900 KB
subtask_1_20.txt AC 20 ms 900 KB