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