QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123922#3863. Evolution of Weaselsaragaz#WA 1ms3464kbC++231.8kb2023-07-14 00:06:032023-07-14 00:06:04

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-14 00:06:04]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3464kb
  • [2023-07-14 00:06:03]
  • Submitted

answer

#include <iostream>
#include <vector>

using namespace std;

void testCase() {
    string s, t;
    cin >> s >> t;

    int n = s.size(), m = t.size();

    s = '$' + s + '$';
    t = '$' + t + '$';

    vector<vector<bool> > dp(n + 5, vector<bool>(m + 5));

    for (int i = n + 1; i > 0; --i) {
        for (int j = m + 1; j > 0; --j) {
            if (s.substr(i) == t.substr(j)) {
                dp[i][j] = true;
            }

            if (s[i] == t[j]) {
                dp[i][j] = dp[i][j] | dp[i + 1][j + 1];
            }

            if (j <= m && t[j] == t[j + 1]) {
                dp[i][j] = dp[i][j] | dp[i][j + 2];
            }

            if (j + 3 <= m + 1 && t[j] == t[j + 2] && t[j] == 'A' && t[j + 1] == t[j + 3] && t[j + 1] == 'B') {
                dp[i][j] = dp[i][j] | dp[i][j + 4];
            }

            if (j + 3 <= m + 1 && t[j] == t[j + 2] && t[j] == 'B' && t[j + 1] == t[j + 3] && t[j + 1] == 'C') {
                dp[i][j] = dp[i][j] | dp[i][j + 4];
            }

            if (i <= n && s[i] == s[i + 1]) {
                dp[i][j] = dp[i][j] | dp[i + 2][j];
            }

            if (i + 3 <= n + 1 && s[i] == s[i + 2] && s[i] == 'A' && s[i + 1] == s[i + 3] && s[i + 1] == 'B') {
                dp[i][j] = dp[i][j] | dp[i + 4][j];
            }

            if (i + 3 <= n + 1 && s[i] == s[i + 2] && s[i] == 'B' && s[i + 1] == s[i + 3] && s[i + 1] == 'C') {
                dp[i][j] = dp[i][j] | dp[i + 4][j];
            }
        }
    }

    if (dp[1][1]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;

    for (int tc = 0; tc < tests; ++tc) {
        testCase();
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3428kb

input:

8
A
B
B
C
C
A
AA
BB
BB
CC
CC
AA
ABAB
BCBC
ABC
CBA

output:

NO
NO
NO
YES
YES
YES
YES
NO

result:

ok 8 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3464kb

input:

81
CA
CA
CB
AA
CA
CC
BA
AA
AC
AA
CC
CC
CA
AA
BC
AA
BA
CA
AA
AA
CB
CA
AC
CB
BB
CB
CC
AA
CB
AB
AB
BC
CB
BC
BC
BC
CC
CA
AA
BB
CB
BB
BC
BA
BC
CB
BA
AB
CA
BB
BB
BC
BC
AB
BC
AC
BB
AC
CB
BA
AA
BC
AB
AC
CA
CB
BC
BB
BC
CC
AA
AB
AB
BB
CB
AC
BB
BB
BA
AC
AA
CA
BB
CA
AA
BA
CA
BA
CB
CB
BA
BC
BC
CA
BB
CC
AC
BA
BB
...

output:

YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO

result:

wrong answer 17th lines differ - expected: 'YES', found: 'NO'