QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#63597 | #2487. Check the String | Sa3tElSefr# | AC ✓ | 13ms | 6484kb | C++20 | 2.6kb | 2022-11-22 20:44:46 | 2022-11-22 20:44:47 |
Judging History
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'