QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65451 | #2487. Check the String | Three_Sannin# | AC ✓ | 17ms | 4724kb | C++14 | 2.6kb | 2022-11-30 21:28:09 | 2022-11-30 21:28:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define ll long long
//#define ld long double
//#define f first
//#define s second
const int N = 1e5+500;
int n , m , lf[N] , rt[N] , id = 2;
string s;
map< pair<int,int> , int> mp;
void dfs(int node)
{
if (!lf[node])
{
char c;
if (node == 1) c = 'a';
else c = 'b';
if (id >= (int)s.size() || c != s[id])
{
cout << "NO\n";
exit(0);
}
id++;
}
else
{
dfs(lf[node]);
dfs(rt[node]);
}
}
void solve()
{
bool f = 0;
vector<int> v = {1 , 2}; //a , b
for(int i=1; i<=m; i++)
{
string str;
cin >> str;
if (f) continue;
if (str == "copy")
{
int tmp = v.back();
v.push_back(tmp);
}
else if (str == "swap")
{
if ((int)v.size() < 2)
{
f = 1;
continue;
}
int lst = v.back();
v.pop_back();
int lstlst = v.back();
v.pop_back();
v.push_back(lst);
v.push_back(lstlst);
}
else if (str == "roll")
{
if ((int)v.size() < 3)
{
f = 1;
continue;
}
vector<int> tmp;
for(int j=(int)v.size()-1; j>=(int)v.size()-3; j--)
tmp.push_back(v[j]);
reverse(tmp.begin() , tmp.end());
v.pop_back();
v.pop_back();
v.pop_back();
v.push_back(tmp[1]);
v.push_back(tmp[2]);
v.push_back(tmp[0]);
}
else
{
if ((int)v.size() < 2)
{
f = 1;
continue;
}
int tmp = v[(int)v.size()-2] , tmp2 = v.back();
v.pop_back();
v.pop_back();
if (mp.count({tmp , tmp2}))
{}
else
{
++id;
mp[{tmp , tmp2}] = id;
}
int num = mp[{tmp , tmp2}];
lf[num] = tmp;
rt[num] = tmp2;
v.push_back(num);
}
}
if (f)
{
cout << "CRASH\n";
return;
}
id = 0;
dfs(v.back());
if (id < s.size()) cout << "NO\n";
else cout << "YES\n";
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> s;
n = s.size();
cin >> m;
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3476kb
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: 0ms
memory: 3524kb
input:
a 0
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
aaba 1 roll
output:
CRASH
result:
ok single line: 'CRASH'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
abbabaaaababbabaaaaaaaabaababbbbbbabbbbabbbabbaabbababaaaaaaaabaababbaabbabbabaabaabbbabbbbabaabbabbbbabaaaaabbbaabaabaabbabbaaaababaaabbbbbbabaabbababbbabbbbbbbababbabbbbaaaaaaabbbbabaaabbabbababababaaabaaaaaaababaabbbabbbabbaabbbabbbabbbbaabaaabbaaabbbbbaabbbaabaabbbbbaaaabaaabbaabaaaaaabaababaaaa...
output:
CRASH
result:
ok single line: 'CRASH'
Test #5:
score: 0
Accepted
time: 7ms
memory: 3568kb
input:
abbabaababbabbbabbbbabaaababbbbbbbabbbbbaabaababbbbababbaabbaabaababababbababbbabababaabaaabbabbbbbabaaaabaaaaaaaaaaabbabbbababbbbbabbbbbbaaaaabaaabbbaababbabbaabaabbbaabbaabbbbababaabaaaabbabbbaabbbbabbbababbaabbaaabaaaabbbabbbbaabababbbabbaababaaaaaabbbaaaabbabbbaaabbabaaaaabbaabbabbbbbbabbabbaaba...
output:
CRASH
result:
ok single line: 'CRASH'
Test #6:
score: 0
Accepted
time: 6ms
memory: 3644kb
input:
baabbbbabababbabbaababaaabbbbabaabbbbbbbaaabbbabababbaaabbabbbbbbabaaabbbbbaababbaabababbbbbaaabbbababaaaaabaabbaaababbaaabbbbbbbabaaaaabaabbabaaabbbabbbbaaaabaaabbbabaabbaabbbbaabaaabaaababbaababbabbbaabbaaaaabababbabbbbbaaabbbbabbaabbbbaaababbbbbbaaabaaabbabbbaaaabbbabbbabbbabaaaaaaabbbbabaabbbbaa...
output:
CRASH
result:
ok single line: 'CRASH'
Test #7:
score: 0
Accepted
time: 4ms
memory: 3660kb
input:
babbbbaaaaaabbbaaabaaababaaababbbaabaaaababaaaaababbbbaabaababbababbababbbbbabaaabbaabbbaabbbaabbbaaaabaaaaaabbbabaabbaaaaababbbbbbbbbaaaabbbbaaaabababaaababaaaabbbaaaaaaababaabaabbbabbbabababbabbbabbabaaabaabaaaabaaabaababababababbbbbbbbabbaaabbbbbaabbbbabbbbbabbbabaabaaaaaaaabbbbbbbbbaabababaabbbb...
output:
CRASH
result:
ok single line: 'CRASH'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
abbaaabbbababbaaaaaaabaabbbbababababaaaabbbbbbbbbaabbbbbabbbaabbabbbbaaabababaaababaabaabaababbbaabaaabbabaaaaaaaababbaabaaaaabaabaabbbbababbbabaaaaababababbaababbaabbbbbbbbbbbbbaabaaaabbbaaaaaabbbbaaaabbbaaabbabbaababababaabaaabababababaabbbbbbbababbabbabbbaaabaaabbaaabbbaaaababbbabbbababbbbabbaabb...
output:
CRASH
result:
ok single line: 'CRASH'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
aaaabbbbbbbababbbbaaaaabbaaababaabbaaabaaabbbbabbbabbbabaababbbaabaaaaaabbbbabaabbaaabbabaabaabaabbbabbbbbaababababababbabbbbbaabbbababbbbbabbbbabbaaababaabbbaaaabbaaabbbbaaabbaabbbabbaaababbaaaabaabaababbabbabbbaabbbaaabaaaabbaabbabbabbbbbbababbbaaaabbabbaaabbaaaababbbaabaababbbbabbbababbababbbabab...
output:
CRASH
result:
ok single line: 'CRASH'
Test #10:
score: 0
Accepted
time: 10ms
memory: 4132kb
input:
aabbabbababaabbbbabbbbaaaaaabbbbabbaabaabbaaabaabbabaabbabbbbbabbbbabbbabababbbaaaaaabababbaaabbbabababbbbbbabbbabbaaababbabbaaabbaaaababababaababbababbbaaabaabbbbaaaabaaababbbbabbbaabababbbbaabbaaabbabbbbaaabbbabbbbabaaaababbbbababbbbababbaababaaabbabbbbbabbabbaabbbabababbabbbaabbaaaaabbaabbbbaaabb...
output:
NO
result:
ok single line: 'NO'
Test #11:
score: 0
Accepted
time: 7ms
memory: 3864kb
input:
abababbaabbabbbbabbbaaabababbbababaaababaabaaabbaaabaaabababbbbbbaaaaaabbbbabbbbabbaaabbbabababbbaababbbabbaaababbbbbbbbbbbbaabaabaaabbabbbaaaabaaaabbbbababbbaabaabaaaaabbbbbaaaaaabbbaabaaabbaaabbbabbbbbbaaababababaabaabbbbbbabaababaaabaaaabaaabbabaabbbbbaaababbabaaaabbaaababbabbbaaababbbbbbbbbaaabb...
output:
YES
result:
ok single line: 'YES'
Test #12:
score: 0
Accepted
time: 4ms
memory: 3652kb
input:
aabbaaabaaaaaabaaaaabaabbbabaabbaaaabbaaababbbbbbbaabbababbbbaabaaabaaabbababbaaaabbabaaaaaaaaaababbababbaaaaababbabbbbaaabbbabaaaabababbbbabababbbaabaabbbbabababaabababbabbaaaabaaabaabbaaabbbaabbbbbabbbaabbabaaaaaaababbaabaaaaabbaabbbababaabbaababababababaaabbbbbababababbbaabaaaabbaaabaabaabababaaa...
output:
YES
result:
ok single line: 'YES'
Test #13:
score: 0
Accepted
time: 9ms
memory: 3700kb
input:
abaabbabbbababaaababbababababbbabaaabaaabbaaaabbbaabbabaabbaabaabaaabbaaaababaabaaababaaabbbbabaaabbbaaaaaaaaabbabaabbbabbaaabababbbbaabbababaaabaabababbabbabbbababbbabaabaaabaaaaabaaaabbabbbbababaaababbbbbabaaaabaaabababbbaabbbaababbabaaabbbabaaaaaabaabbaaaaabaaabaabbbbbaaabaaaaaabbbaaabbababaabbba...
output:
YES
result:
ok single line: 'YES'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
aabbbbbaabababbabbbaabababbabbabbbabbbbaababbaaabbabababaaabbaabaaaabbbbbbbbbaaabbbbbaaaababaaabbabbaaaababababbabaabaaabaaabbbbbbbbababababbaabaabbaaaaaababbaaaaabbaaaababbabaabbaaabaabbbabaaabaaaababbbbbababaabbbaabaabbaabbbbabbaabaaaabbaabaaabaabababaaaaabbabbbbabbbbbbabababbabbabbbaabbabaababbaa...
output:
YES
result:
ok single line: 'YES'
Test #15:
score: 0
Accepted
time: 5ms
memory: 3724kb
input:
bbaabbabbbbaabababbbbaabbbababbbabbbbabababaaabbbbaaabaabbabaaabaaaabaabababbbbaaababaaaaababbaabbbbbbabbbabbbbbabbabbabaabbbbbbbabbbaaaaaaabbabbabbbbbaaaabbabbbaaaaaaababbbabababaaababbbabbabbaaababaabaaaabbabbababbabababaabbaabbbaabbaaabababaabaaaaaaaabaababbbabaababaaabaaaabbaabaababbbabababaabba...
output:
YES
result:
ok single line: 'YES'
Test #16:
score: 0
Accepted
time: 16ms
memory: 4644kb
input:
aaabbabbbabbbababbbaababaabbbaaabbaaabbabbbbaabaabbabababbbbbaabbaaaabbbaaabababbabbaaabaaaabaaaaabbbbbbaaaaaabababbbabaabbabaaabaaababaaabbbbaaabbaabbbababbbbabbaaabababbabaabaabababaababaabbbaaababaababaaababaababaaababaabbabaaaabbbbabbbabbaababbbbbbbbbaabbabbbbbbabbababbbaabbbabbbbaabbabaabababab...
output:
YES
result:
ok single line: 'YES'
Test #17:
score: 0
Accepted
time: 17ms
memory: 4408kb
input:
bbabbabbbbbbbbabaabbbbaabaababbbababaabaababbbbbabbabbbbaaaaaaaaabbbaaabbaabaabbaaaaababbbababaabaaabbbabaaabbabbabaabbbaabbabaaaabbbbbabaaabbbabaabbbbaaaaabbaaaaabbaaabbbbaababbabbabbbbabbbaaaaaaabbaabbbbaabbaabbbbbabbaaababbbbaaababaaaabbaaaabbabbbbbbbabababaabababbbbabaaabbbaabbaabbaaabbbababbbab...
output:
YES
result:
ok single line: 'YES'
Test #18:
score: 0
Accepted
time: 17ms
memory: 4464kb
input:
bbbabaabaaabbabaaaaabbbbbbabbbbaaaaabababbabbabaaaaaabbbbaaabaabbababbbaaababbbbabababbabaababbbbabbbabbaaababbaabbbaaabaabbaabbbbabbbbbbbabbbbbabbbaabbbabaaaababbaaaabbbbbbabbaaabaaaabbbaabababaaaaaaabbbaaaabbbbbbbbabaabbaaaababaaaaaaaabaabbbabbabaababaabbaaababbbabababbbaaaabbaaabaabaabbbaabbbaabb...
output:
YES
result:
ok single line: 'YES'
Test #19:
score: 0
Accepted
time: 13ms
memory: 4320kb
input:
aababaabbabababbbabbaabbbbaaaabbababbbbbbabaaabaabbbaaabaabaababaabaabbaaabaaaabbabbbaaabaabbbbabbbbabbabaaabaaaabbaaababbbbaaabbbbabbabbbbbabbbbbbababbabbaababbbababababbbbbbbaabaabbabbaaabababaabaaabbaaaaaaabababbaaababaabbbaabaabbbabaaabbbbbaaabbabbabaabaabbbabbbabbabbbaabaaabbabbaabbbabaaabbbbab...
output:
NO
result:
ok single line: 'NO'
Test #20:
score: 0
Accepted
time: 14ms
memory: 4516kb
input:
abaabaabababaaaaaababaabbbbaabaaabbbabbbabaababbabbbaaaabababaababaababbabbabaabaaabababbbbabbbaaaaaabbaababbbbaabbbabbaabbbbbbabbabbabbaabbbabbabaabbaaaaaabbbbaaaaabababbabbabbbbabbabbababbbaabababaaaaababbbaaabaaabbabaababbaaabaabbaababbabaabaaaaaaabbbbabaabaabbaabbbbbbbbbbaaaaabbbbbbaaaaabbaaaaaa...
output:
NO
result:
ok single line: 'NO'
Test #21:
score: 0
Accepted
time: 13ms
memory: 4488kb
input:
babbaaaaaababaabbabbabaabbbaabbbbababbbbbaabbaaaaaaaabbaabaabbbabbbaaabbbabbbababbaaabbaaabbaabbababbababbaaaabbbabaaabbabaabaaabbababaaabbababbaaabaaaaaababaaababbaaabbbababbbbbbaabbabbaababbbbbbaabbaabbaaababaabbaababbbababababbbbbbaaaabbabbabaaabaabbababbabbaabaabbaabbbabababaabaabbabbbbbabbabaaa...
output:
NO
result:
ok single line: 'NO'
Test #22:
score: 0
Accepted
time: 17ms
memory: 4724kb
input:
babbabbbbbbbbbbbbbbbbbbabbaaabbaababbaaaaabbaabbaabbaaaaabbabaabababbbaaababaaabaaaabbbbbbbbbbbabaabbabbbababbbababbbaaabaaaaabbbabaababbabbbbabbbbbaabaaaababaabbbbaababbabbaabbbaaababaabaaaaaaaabbabababbaabbbbabbbbabababababbbabaabbbabaabbbbabaabbbbbbbabbaaaabbabaababbbbaabaaaabbabaaabaaaabbbbbbaaa...
output:
NO
result:
ok single line: 'NO'
Test #23:
score: 0
Accepted
time: 6ms
memory: 3688kb
input:
ababbbbbaabaababbbbababbbbaaaababbbaaaababbaaaaabbbabbaaaaabaaabbababbabbabbbbababbbbaabbbbbbbabaaaaaaaabbaaababbaabaaabaaabaaaabbaababaabbbbabbabbabbbbaaabbabbabababaaababbaabbbabbabbabbbbababbababaaaabbabbbabaabaaabbbaabbaaabbaabbaabbbaabaaaaabbabbbbaaaabaabaabababaabbbbaaabbbaabbaababbbabbaabbbbb...
output:
NO
result:
ok single line: 'NO'
Test #24:
score: 0
Accepted
time: 4ms
memory: 3556kb
input:
babbaabababbbabbabaaabaabaabbabaabaabaabbbbabbbabaaabbaabbbabbbbbbabaaabbaabaabbbabaaaaababaaaababaabaaaaabbbbaabbaaabbaabbaabaaababbaaaabbbbbaababaaaaaaababbbbbbbaaaababaaaaaaabababbbbbaaaababaabbbaaaabbbaaaaaaaaabbbbababbbbabbbbaabbbbabaabbbbbbbbaababababbabbbbabbbaaaaababbaaabbbbaabbaaaaaabbbaaba...
output:
CRASH
result:
ok single line: 'CRASH'