提出 #4788749

ソースコード 拡げる

#include <iostream>
#include <vector>

using namespace std;


int find_l(int N, int Q, string &s, vector<char> &ts, vector<char> &ds) {
//    左に落ちるのを探す
    int l_index = 0, r_index = N + 1;
    while ((r_index - l_index) > 1) {
        int target_index = (l_index + r_index) / 2;
        int current_cell = target_index;
        for (int i = 0; i < Q; i++) {
            char t = ts[i], d = ds[i];
            if (s[current_cell - 1] == t) {
                if (d == 'L') {
                    current_cell--;
                } else {
                    current_cell++;
                }
            }
            if (current_cell == 0) break;
            if (current_cell == (N + 1)) break;
        }
        if (current_cell != 0) {
            r_index = target_index;
        } else {
            l_index = target_index;
        }
    }
    return l_index;
}

int find_r(int N, int Q, string &s, vector<char> &ts, vector<char> &ds) {
//    右に落ちるのを探す
    int l_index = 0, r_index = N + 1;
    while ((r_index - l_index) > 1) {
        int target_index = (l_index + r_index) / 2;
        int current_cell = target_index;
        for (int i = 0; i < Q; i++) {
            char t = ts[i], d = ds[i];
            if (s[current_cell - 1] == t) {
                if (d == 'L') {
                    current_cell--;
                } else {
                    current_cell++;
                }
            }
            if (current_cell == (N + 1)) break;
            if (current_cell == 0) break;
        }
        if (current_cell != (N + 1)) {
            l_index = target_index;
        } else {
            r_index = target_index;
        }
    }
    return r_index;
}


int main() {
    int N, Q;
    cin >> N >> Q;
    string s;
    cin >> s;
    vector<char> ts(Q), ds(Q);
    for (int i = 0; i < Q; i++) {
        char t, d;
        cin >> t >> d;
        ts[i] = t;
        ds[i] = d;
    }

    int l_ans = find_l(N, Q, s, ts, ds);
    int r_ans = find_r(N, Q, s, ts, ds);
    cout << r_ans - l_ans - 1 << endl;
}

提出情報

提出日時
問題 C - Snuke the Wizard
ユーザ gdmiwasawa
言語 C++14 (GCC 5.4.1)
得点 500
コード長 2136 Byte
結果 AC
実行時間 74 ms
メモリ 900 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 29
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 1 ms 256 KiB
sample_02.txt AC 1 ms 256 KiB
sample_03.txt AC 1 ms 256 KiB
test_01.txt AC 52 ms 900 KiB
test_02.txt AC 52 ms 900 KiB
test_03.txt AC 54 ms 900 KiB
test_04.txt AC 53 ms 900 KiB
test_05.txt AC 55 ms 900 KiB
test_06.txt AC 52 ms 900 KiB
test_07.txt AC 57 ms 900 KiB
test_08.txt AC 57 ms 900 KiB
test_09.txt AC 56 ms 896 KiB
test_10.txt AC 53 ms 896 KiB
test_11.txt AC 51 ms 896 KiB
test_12.txt AC 51 ms 900 KiB
test_13.txt AC 56 ms 900 KiB
test_14.txt AC 57 ms 900 KiB
test_15.txt AC 60 ms 900 KiB
test_16.txt AC 56 ms 900 KiB
test_17.txt AC 51 ms 900 KiB
test_18.txt AC 39 ms 900 KiB
test_19.txt AC 74 ms 900 KiB
test_20.txt AC 60 ms 640 KiB
test_21.txt AC 71 ms 900 KiB
test_22.txt AC 58 ms 900 KiB
test_23.txt AC 53 ms 900 KiB
test_24.txt AC 47 ms 896 KiB
test_25.txt AC 44 ms 772 KiB
test_26.txt AC 27 ms 644 KiB