QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#63597#2487. Check the StringSa3tElSefr#AC ✓13ms6484kbC++202.6kb2022-11-22 20:44:462022-11-22 20:44:47

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.
  • [2022-11-22 20:44:47]
  • Judged
  • Verdict: AC
  • Time: 13ms
  • Memory: 6484kb
  • [2022-11-22 20:44:46]
  • Submitted

answer

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double


const int N = 1000 + 5, mod = 998244353, OO = 1e5 + 5;

string s;

struct node {
    char type;
    int length;
    vector<node*> children;
};

int n;
stack<node*> st;

void crash() {
    cout << "CRASH\n";
    exit(0);
}

node *merge(node *a, node *b) {
    node *ret = new node();
    if (a->length + b->length > OO) {
        ret->length = OO;
    } else {
        ret->length = a->length + b->length;
        ret->children.push_back(a);
        ret->children.push_back(b);
    }
    return ret;
}

int idx = 0;
bool can = true;

void solve(node *u) {
    if (u->children.empty()) {
        if (u->type != s[idx]) {
            can = false;
        } else {
            ++idx;
        }
    } else {
        for (auto &v : u->children) {
            solve(v);
        }
    }
}

bool solve() {
    solve(st.top());
    return can && idx == st.top()->length;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    cin >> n;
    node *a = new node(), *b = new node();
    a->type = 'a';
    a->length = 1;
    b->type = 'b';
    b->length = 1;
    st.push(a);
    st.push(b);
    while (n--) {
        string s;
        cin >> s;
        if (s == "copy") {
            st.push(st.top());
        } else if (s == "swap") {
            if (st.size() < 2) {
                crash();
            } else {
                auto y = st.top();
                st.pop();
                auto x = st.top();
                st.pop();
                st.push(y);
                st.push(x);
            }
        } else if (s == "roll") {
            if (st.size() < 3) {
                crash();
            } else {
                auto z = st.top();
                st.pop();
                auto y = st.top();
                st.pop();
                auto x = st.top();
                st.pop();
                st.push(y);
                st.push(z);
                st.push(x);
            }
        } else {
            if (st.size() < 2) {
                crash();
            } else {
                auto y = st.top();
                st.pop();
                auto x = st.top();
                st.pop();
                st.push(merge(x, y));
            }
        }
    }
    if (st.top()->length != s.size()) {
        cout << "NO\n";
    } else {
        cout << (solve() ? "YES" : "NO") << '\n';
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3356kb

input:

ababa
9
swap
copy
roll
fuse
copy
fuse
copy
roll
fuse

output:

YES

result:

ok single line: 'YES'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

a
0

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3260kb

input:

aaba
1
roll

output:

CRASH

result:

ok single line: 'CRASH'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3372kb

input:

abbabaaaababbabaaaaaaaabaababbbbbbabbbbabbbabbaabbababaaaaaaaabaababbaabbabbabaabaabbbabbbbabaabbabbbbabaaaaabbbaabaabaabbabbaaaababaaabbbbbbabaabbababbbabbbbbbbababbabbbbaaaaaaabbbbabaaabbabbababababaaabaaaaaaababaabbbabbbabbaabbbabbbabbbbaabaaabbaaabbbbbaabbbaabaabbbbbaaaabaaabbaabaaaaaabaababaaaa...

output:

CRASH

result:

ok single line: 'CRASH'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3356kb

input:

abbabaababbabbbabbbbabaaababbbbbbbabbbbbaabaababbbbababbaabbaabaababababbababbbabababaabaaabbabbbbbabaaaabaaaaaaaaaaabbabbbababbbbbabbbbbbaaaaabaaabbbaababbabbaabaabbbaabbaabbbbababaabaaaabbabbbaabbbbabbbababbaabbaaabaaaabbbabbbbaabababbbabbaababaaaaaabbbaaaabbabbbaaabbabaaaaabbaabbabbbbbbabbabbaaba...

output:

CRASH

result:

ok single line: 'CRASH'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

baabbbbabababbabbaababaaabbbbabaabbbbbbbaaabbbabababbaaabbabbbbbbabaaabbbbbaababbaabababbbbbaaabbbababaaaaabaabbaaababbaaabbbbbbbabaaaaabaabbabaaabbbabbbbaaaabaaabbbabaabbaabbbbaabaaabaaababbaababbabbbaabbaaaaabababbabbbbbaaabbbbabbaabbbbaaababbbbbbaaabaaabbabbbaaaabbbabbbabbbabaaaaaaabbbbabaabbbbaa...

output:

CRASH

result:

ok single line: 'CRASH'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

babbbbaaaaaabbbaaabaaababaaababbbaabaaaababaaaaababbbbaabaababbababbababbbbbabaaabbaabbbaabbbaabbbaaaabaaaaaabbbabaabbaaaaababbbbbbbbbaaaabbbbaaaabababaaababaaaabbbaaaaaaababaabaabbbabbbabababbabbbabbabaaabaabaaaabaaabaababababababbbbbbbbabbaaabbbbbaabbbbabbbbbabbbabaabaaaaaaaabbbbbbbbbaabababaabbbb...

output:

CRASH

result:

ok single line: 'CRASH'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

abbaaabbbababbaaaaaaabaabbbbababababaaaabbbbbbbbbaabbbbbabbbaabbabbbbaaabababaaababaabaabaababbbaabaaabbabaaaaaaaababbaabaaaaabaabaabbbbababbbabaaaaababababbaababbaabbbbbbbbbbbbbaabaaaabbbaaaaaabbbbaaaabbbaaabbabbaababababaabaaabababababaabbbbbbbababbabbabbbaaabaaabbaaabbbaaaababbbabbbababbbbabbaabb...

output:

CRASH

result:

ok single line: 'CRASH'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

aaaabbbbbbbababbbbaaaaabbaaababaabbaaabaaabbbbabbbabbbabaababbbaabaaaaaabbbbabaabbaaabbabaabaabaabbbabbbbbaababababababbabbbbbaabbbababbbbbabbbbabbaaababaabbbaaaabbaaabbbbaaabbaabbbabbaaababbaaaabaabaababbabbabbbaabbbaaabaaaabbaabbabbabbbbbbababbbaaaabbabbaaabbaaaababbbaabaababbbbabbbababbababbbabab...

output:

CRASH

result:

ok single line: 'CRASH'

Test #10:

score: 0
Accepted
time: 7ms
memory: 4104kb

input:

aabbabbababaabbbbabbbbaaaaaabbbbabbaabaabbaaabaabbabaabbabbbbbabbbbabbbabababbbaaaaaabababbaaabbbabababbbbbbabbbabbaaababbabbaaabbaaaababababaababbababbbaaabaabbbbaaaabaaababbbbabbbaabababbbbaabbaaabbabbbbaaabbbabbbbabaaaababbbbababbbbababbaababaaabbabbbbbabbabbaabbbabababbabbbaabbaaaaabbaabbbbaaabb...

output:

NO

result:

ok single line: 'NO'

Test #11:

score: 0
Accepted
time: 6ms
memory: 4232kb

input:

abababbaabbabbbbabbbaaabababbbababaaababaabaaabbaaabaaabababbbbbbaaaaaabbbbabbbbabbaaabbbabababbbaababbbabbaaababbbbbbbbbbbbaabaabaaabbabbbaaaabaaaabbbbababbbaabaabaaaaabbbbbaaaaaabbbaabaaabbaaabbbabbbbbbaaababababaabaabbbbbbabaababaaabaaaabaaabbabaabbbbbaaababbabaaaabbaaababbabbbaaababbbbbbbbbaaabb...

output:

YES

result:

ok single line: 'YES'

Test #12:

score: 0
Accepted
time: 5ms
memory: 4076kb

input:

aabbaaabaaaaaabaaaaabaabbbabaabbaaaabbaaababbbbbbbaabbababbbbaabaaabaaabbababbaaaabbabaaaaaaaaaababbababbaaaaababbabbbbaaabbbabaaaabababbbbabababbbaabaabbbbabababaabababbabbaaaabaaabaabbaaabbbaabbbbbabbbaabbabaaaaaaababbaabaaaaabbaabbbababaabbaababababababaaabbbbbababababbbaabaaaabbaaabaabaabababaaa...

output:

YES

result:

ok single line: 'YES'

Test #13:

score: 0
Accepted
time: 6ms
memory: 4140kb

input:

abaabbabbbababaaababbababababbbabaaabaaabbaaaabbbaabbabaabbaabaabaaabbaaaababaabaaababaaabbbbabaaabbbaaaaaaaaabbabaabbbabbaaabababbbbaabbababaaabaabababbabbabbbababbbabaabaaabaaaaabaaaabbabbbbababaaababbbbbabaaaabaaabababbbaabbbaababbabaaabbbabaaaaaabaabbaaaaabaaabaabbbbbaaabaaaaaabbbaaabbababaabbba...

output:

YES

result:

ok single line: 'YES'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4044kb

input:

aabbbbbaabababbabbbaabababbabbabbbabbbbaababbaaabbabababaaabbaabaaaabbbbbbbbbaaabbbbbaaaababaaabbabbaaaababababbabaabaaabaaabbbbbbbbababababbaabaabbaaaaaababbaaaaabbaaaababbabaabbaaabaabbbabaaabaaaababbbbbababaabbbaabaabbaabbbbabbaabaaaabbaabaaabaabababaaaaabbabbbbabbbbbbabababbabbabbbaabbabaababbaa...

output:

YES

result:

ok single line: 'YES'

Test #15:

score: 0
Accepted
time: 4ms
memory: 3812kb

input:

bbaabbabbbbaabababbbbaabbbababbbabbbbabababaaabbbbaaabaabbabaaabaaaabaabababbbbaaababaaaaababbaabbbbbbabbbabbbbbabbabbabaabbbbbbbabbbaaaaaaabbabbabbbbbaaaabbabbbaaaaaaababbbabababaaababbbabbabbaaababaabaaaabbabbababbabababaabbaabbbaabbaaabababaabaaaaaaaabaababbbabaababaaabaaaabbaabaababbbabababaabba...

output:

YES

result:

ok single line: 'YES'

Test #16:

score: 0
Accepted
time: 7ms
memory: 6052kb

input:

aaabbabbbabbbababbbaababaabbbaaabbaaabbabbbbaabaabbabababbbbbaabbaaaabbbaaabababbabbaaabaaaabaaaaabbbbbbaaaaaabababbbabaabbabaaabaaababaaabbbbaaabbaabbbababbbbabbaaabababbabaabaabababaababaabbbaaababaababaaababaababaaababaabbabaaaabbbbabbbabbaababbbbbbbbbaabbabbbbbbabbababbbaabbbabbbbaabbabaabababab...

output:

YES

result:

ok single line: 'YES'

Test #17:

score: 0
Accepted
time: 6ms
memory: 6484kb

input:

bbabbabbbbbbbbabaabbbbaabaababbbababaabaababbbbbabbabbbbaaaaaaaaabbbaaabbaabaabbaaaaababbbababaabaaabbbabaaabbabbabaabbbaabbabaaaabbbbbabaaabbbabaabbbbaaaaabbaaaaabbaaabbbbaababbabbabbbbabbbaaaaaaabbaabbbbaabbaabbbbbabbaaababbbbaaababaaaabbaaaabbabbbbbbbabababaabababbbbabaaabbbaabbaabbaaabbbababbbab...

output:

YES

result:

ok single line: 'YES'

Test #18:

score: 0
Accepted
time: 13ms
memory: 6180kb

input:

bbbabaabaaabbabaaaaabbbbbbabbbbaaaaabababbabbabaaaaaabbbbaaabaabbababbbaaababbbbabababbabaababbbbabbbabbaaababbaabbbaaabaabbaabbbbabbbbbbbabbbbbabbbaabbbabaaaababbaaaabbbbbbabbaaabaaaabbbaabababaaaaaaabbbaaaabbbbbbbbabaabbaaaababaaaaaaaabaabbbabbabaababaabbaaababbbabababbbaaaabbaaabaabaabbbaabbbaabb...

output:

YES

result:

ok single line: 'YES'

Test #19:

score: 0
Accepted
time: 4ms
memory: 4152kb

input:

aababaabbabababbbabbaabbbbaaaabbababbbbbbabaaabaabbbaaabaabaababaabaabbaaabaaaabbabbbaaabaabbbbabbbbabbabaaabaaaabbaaababbbbaaabbbbabbabbbbbabbbbbbababbabbaababbbababababbbbbbbaabaabbabbaaabababaabaaabbaaaaaaabababbaaababaabbbaabaabbbabaaabbbbbaaabbabbabaabaabbbabbbabbabbbaabaaabbabbaabbbabaaabbbbab...

output:

NO

result:

ok single line: 'NO'

Test #20:

score: 0
Accepted
time: 5ms
memory: 4108kb

input:

abaabaabababaaaaaababaabbbbaabaaabbbabbbabaababbabbbaaaabababaababaababbabbabaabaaabababbbbabbbaaaaaabbaababbbbaabbbabbaabbbbbbabbabbabbaabbbabbabaabbaaaaaabbbbaaaaabababbabbabbbbabbabbababbbaabababaaaaababbbaaabaaabbabaababbaaabaabbaababbabaabaaaaaaabbbbabaabaabbaabbbbbbbbbbaaaaabbbbbbaaaaabbaaaaaa...

output:

NO

result:

ok single line: 'NO'

Test #21:

score: 0
Accepted
time: 8ms
memory: 4252kb

input:

babbaaaaaababaabbabbabaabbbaabbbbababbbbbaabbaaaaaaaabbaabaabbbabbbaaabbbabbbababbaaabbaaabbaabbababbababbaaaabbbabaaabbabaabaaabbababaaabbababbaaabaaaaaababaaababbaaabbbababbbbbbaabbabbaababbbbbbaabbaabbaaababaabbaababbbababababbbbbbaaaabbabbabaaabaabbababbabbaabaabbaabbbabababaabaabbabbbbbabbabaaa...

output:

NO

result:

ok single line: 'NO'

Test #22:

score: 0
Accepted
time: 7ms
memory: 4488kb

input:

babbabbbbbbbbbbbbbbbbbbabbaaabbaababbaaaaabbaabbaabbaaaaabbabaabababbbaaababaaabaaaabbbbbbbbbbbabaabbabbbababbbababbbaaabaaaaabbbabaababbabbbbabbbbbaabaaaababaabbbbaababbabbaabbbaaababaabaaaaaaaabbabababbaabbbbabbbbabababababbbabaabbbabaabbbbabaabbbbbbbabbaaaabbabaababbbbaabaaaabbabaaabaaaabbbbbbaaa...

output:

NO

result:

ok single line: 'NO'

Test #23:

score: 0
Accepted
time: 4ms
memory: 3564kb

input:

ababbbbbaabaababbbbababbbbaaaababbbaaaababbaaaaabbbabbaaaaabaaabbababbabbabbbbababbbbaabbbbbbbabaaaaaaaabbaaababbaabaaabaaabaaaabbaababaabbbbabbabbabbbbaaabbabbabababaaababbaabbbabbabbabbbbababbababaaaabbabbbabaabaaabbbaabbaaabbaabbaabbbaabaaaaabbabbbbaaaabaabaabababaabbbbaaabbbaabbaababbbabbaabbbbb...

output:

NO

result:

ok single line: 'NO'

Test #24:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

babbaabababbbabbabaaabaabaabbabaabaabaabbbbabbbabaaabbaabbbabbbbbbabaaabbaabaabbbabaaaaababaaaababaabaaaaabbbbaabbaaabbaabbaabaaababbaaaabbbbbaababaaaaaaababbbbbbbaaaababaaaaaaabababbbbbaaaababaabbbaaaabbbaaaaaaaaabbbbababbbbabbbbaabbbbabaabbbbbbbbaababababbabbbbabbbaaaaababbaaabbbbaabbaaaaaabbbaaba...

output:

CRASH

result:

ok single line: 'CRASH'