QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395111 | #2487. Check the String | Massachusetts Institute of Terriers (Yi Du, Mutiraj Laksanawisit)# | AC ✓ | 29ms | 35316kb | C++20 | 3.4kb | 2024-04-21 04:44:50 | 2024-04-21 04:44:50 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
stack<pair<int, int>> S;
map<int, pair<int, int>> P;
string to_string(pair<queue<char>, queue<char>> s)
{
string ret;
stack<char> temp;
while(!s.first.empty())
{
temp.push(s.first.front());
s.first.pop();
}
while(!temp.empty())
{
ret += temp.top();
temp.pop();
}
while(!s.second.empty())
{
ret += s.second.front();
s.second.pop();
}
return ret;
}
pair<queue<char>, queue<char>> find_string(int n)
{
if(n == 1)
{
queue<char> q1({'a'}), q2;
return make_pair(q1, q2);
}
if(n == 2)
{
queue<char> q1({'b'}), q2;
return make_pair(q1, q2);
}
int x = P[n].first, y = P[n].second;
pair<queue<char>, queue<char>> a = find_string(x);
pair<queue<char>, queue<char>> b = find_string(y);
if(a.first.size() + a.second.size() < b.first.size() + b.second.size())
{
stack<char> temp;
while(!a.second.empty())
{
temp.push(a.second.front());
a.second.pop();
}
while(!temp.empty())
{
b.first.push(temp.top());
temp.pop();
}
while(!a.first.empty())
{
b.first.push(a.first.front());
a.first.pop();
}
return b;
}
else
{
stack<char> temp;
while(!b.first.empty())
{
temp.push(b.first.front());
b.first.pop();
}
while(!temp.empty())
{
a.second.push(temp.top());
temp.pop();
}
while(!b.second.empty())
{
a.second.push(b.second.front());
b.second.pop();
}
return a;
}
}
void COPY()
{
S.push(S.top());
}
void SWAP()
{
if(S.size() < 2)
{
cout << "CRASH";
exit(0);
}
else
{
pair<int, int> a = S.top();
S.pop();
pair<int, int> b = S.top();
S.pop();
S.push(a);
S.push(b);
}
}
void ROLL()
{
if(S.size() < 3)
{
cout << "CRASH";
exit(0);
}
else
{
pair<int, int> a = S.top();
S.pop();
pair<int, int> b = S.top();
S.pop();
pair<int, int> c = S.top();
S.pop();
S.push(b);
S.push(a);
S.push(c);
}
}
void FUSE()
{
if(S.size() < 2)
{
cout << "CRASH";
exit(0);
}
else
{
pair<int, int> a = S.top();
S.pop();
pair<int, int> b = S.top();
S.pop();
S.push({P.size() + 3, min(a.second + b.second, (int) 1e9)});
P[P.size() + 3] = {b.first, a.first};
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
S.push({1, 1});
S.push({2, 1});
string s;
cin >> s;
int n;
cin >> n;
while(n-->0)
{
string command;
cin >> command;
if(command == "copy") COPY();
else if(command == "swap") SWAP();
else if(command == "roll") ROLL();
else if(command == "fuse") FUSE();
}
if(S.top().second != s.size() || to_string(find_string(S.top().first)) != s) cout << "NO";
else cout << "YES";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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: 3624kb
input:
a 0
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
aaba 1 roll
output:
CRASH
result:
ok single line: 'CRASH'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
abbabaaaababbabaaaaaaaabaababbbbbbabbbbabbbabbaabbababaaaaaaaabaababbaabbabbabaabaabbbabbbbabaabbabbbbabaaaaabbbaabaabaabbabbaaaababaaabbbbbbabaabbababbbabbbbbbbababbabbbbaaaaaaabbbbabaaabbabbababababaaabaaaaaaababaabbbabbbabbaabbbabbbabbbbaabaaabbaaabbbbbaabbbaabaabbbbbaaaabaaabbaabaaaaaabaababaaaa...
output:
CRASH
result:
ok single line: 'CRASH'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
abbabaababbabbbabbbbabaaababbbbbbbabbbbbaabaababbbbababbaabbaabaababababbababbbabababaabaaabbabbbbbabaaaabaaaaaaaaaaabbabbbababbbbbabbbbbbaaaaabaaabbbaababbabbaabaabbbaabbaabbbbababaabaaaabbabbbaabbbbabbbababbaabbaaabaaaabbbabbbbaabababbbabbaababaaaaaabbbaaaabbabbbaaabbabaaaaabbaabbabbbbbbabbabbaaba...
output:
CRASH
result:
ok single line: 'CRASH'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
baabbbbabababbabbaababaaabbbbabaabbbbbbbaaabbbabababbaaabbabbbbbbabaaabbbbbaababbaabababbbbbaaabbbababaaaaabaabbaaababbaaabbbbbbbabaaaaabaabbabaaabbbabbbbaaaabaaabbbabaabbaabbbbaabaaabaaababbaababbabbbaabbaaaaabababbabbbbbaaabbbbabbaabbbbaaababbbbbbaaabaaabbabbbaaaabbbabbbabbbabaaaaaaabbbbabaabbbbaa...
output:
CRASH
result:
ok single line: 'CRASH'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
babbbbaaaaaabbbaaabaaababaaababbbaabaaaababaaaaababbbbaabaababbababbababbbbbabaaabbaabbbaabbbaabbbaaaabaaaaaabbbabaabbaaaaababbbbbbbbbaaaabbbbaaaabababaaababaaaabbbaaaaaaababaabaabbbabbbabababbabbbabbabaaabaabaaaabaaabaababababababbbbbbbbabbaaabbbbbaabbbbabbbbbabbbabaabaaaaaaaabbbbbbbbbaabababaabbbb...
output:
CRASH
result:
ok single line: 'CRASH'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
abbaaabbbababbaaaaaaabaabbbbababababaaaabbbbbbbbbaabbbbbabbbaabbabbbbaaabababaaababaabaabaababbbaabaaabbabaaaaaaaababbaabaaaaabaabaabbbbababbbabaaaaababababbaababbaabbbbbbbbbbbbbaabaaaabbbaaaaaabbbbaaaabbbaaabbabbaababababaabaaabababababaabbbbbbbababbabbabbbaaabaaabbaaabbbaaaababbbabbbababbbbabbaabb...
output:
CRASH
result:
ok single line: 'CRASH'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
aaaabbbbbbbababbbbaaaaabbaaababaabbaaabaaabbbbabbbabbbabaababbbaabaaaaaabbbbabaabbaaabbabaabaabaabbbabbbbbaababababababbabbbbbaabbbababbbbbabbbbabbaaababaabbbaaaabbaaabbbbaaabbaabbbabbaaababbaaaabaabaababbabbabbbaabbbaaabaaaabbaabbabbabbbbbbababbbaaaabbabbaaabbaaaababbbaabaababbbbabbbababbababbbabab...
output:
CRASH
result:
ok single line: 'CRASH'
Test #10:
score: 0
Accepted
time: 4ms
memory: 4404kb
input:
aabbabbababaabbbbabbbbaaaaaabbbbabbaabaabbaaabaabbabaabbabbbbbabbbbabbbabababbbaaaaaabababbaaabbbabababbbbbbabbbabbaaababbabbaaabbaaaababababaababbababbbaaabaabbbbaaaabaaababbbbabbbaabababbbbaabbaaabbabbbbaaabbbabbbbabaaaababbbbababbbbababbaababaaabbabbbbbabbabbaabbbabababbabbbaabbaaaaabbaabbbbaaabb...
output:
NO
result:
ok single line: 'NO'
Test #11:
score: 0
Accepted
time: 5ms
memory: 13424kb
input:
abababbaabbabbbbabbbaaabababbbababaaababaabaaabbaaabaaabababbbbbbaaaaaabbbbabbbbabbaaabbbabababbbaababbbabbaaababbbbbbbbbbbbaabaabaaabbabbbaaaabaaaabbbbababbbaabaabaaaaabbbbbaaaaaabbbaabaaabbaaabbbabbbbbbaaababababaabaabbbbbbabaababaaabaaaabaaabbabaabbbbbaaababbabaaaabbaaababbabbbaaababbbbbbbbbaaabb...
output:
YES
result:
ok single line: 'YES'
Test #12:
score: 0
Accepted
time: 6ms
memory: 12228kb
input:
aabbaaabaaaaaabaaaaabaabbbabaabbaaaabbaaababbbbbbbaabbababbbbaabaaabaaabbababbaaaabbabaaaaaaaaaababbababbaaaaababbabbbbaaabbbabaaaabababbbbabababbbaabaabbbbabababaabababbabbaaaabaaabaabbaaabbbaabbbbbabbbaabbabaaaaaaababbaabaaaaabbaabbbababaabbaababababababaaabbbbbababababbbaabaaaabbaaabaabaabababaaa...
output:
YES
result:
ok single line: 'YES'
Test #13:
score: 0
Accepted
time: 7ms
memory: 13340kb
input:
abaabbabbbababaaababbababababbbabaaabaaabbaaaabbbaabbabaabbaabaabaaabbaaaababaabaaababaaabbbbabaaabbbaaaaaaaaabbabaabbbabbaaabababbbbaabbababaaabaabababbabbabbbababbbabaabaaabaaaaabaaaabbabbbbababaaababbbbbabaaaabaaabababbbaabbbaababbabaaabbbabaaaaaabaabbaaaaabaaabaabbbbbaaabaaaaaabbbaaabbababaabbba...
output:
YES
result:
ok single line: 'YES'
Test #14:
score: 0
Accepted
time: 3ms
memory: 10272kb
input:
aabbbbbaabababbabbbaabababbabbabbbabbbbaababbaaabbabababaaabbaabaaaabbbbbbbbbaaabbbbbaaaababaaabbabbaaaababababbabaabaaabaaabbbbbbbbababababbaabaabbaaaaaababbaaaaabbaaaababbabaabbaaabaabbbabaaabaaaababbbbbababaabbbaabaabbaabbbbabbaabaaaabbaabaaabaabababaaaaabbabbbbabbbbbbabababbabbabbbaabbabaababbaa...
output:
YES
result:
ok single line: 'YES'
Test #15:
score: 0
Accepted
time: 7ms
memory: 9344kb
input:
bbaabbabbbbaabababbbbaabbbababbbabbbbabababaaabbbbaaabaabbabaaabaaaabaabababbbbaaababaaaaababbaabbbbbbabbbabbbbbabbabbabaabbbbbbbabbbaaaaaaabbabbabbbbbaaaabbabbbaaaaaaababbbabababaaababbbabbabbaaababaabaaaabbabbababbabababaabbaabbbaabbaaabababaabaaaaaaaabaababbbabaababaaabaaaabbaabaababbbabababaabba...
output:
YES
result:
ok single line: 'YES'
Test #16:
score: 0
Accepted
time: 20ms
memory: 33004kb
input:
aaabbabbbabbbababbbaababaabbbaaabbaaabbabbbbaabaabbabababbbbbaabbaaaabbbaaabababbabbaaabaaaabaaaaabbbbbbaaaaaabababbbabaabbabaaabaaababaaabbbbaaabbaabbbababbbbabbaaabababbabaabaabababaababaabbbaaababaababaaababaababaaababaabbabaaaabbbbabbbabbaababbbbbbbbbaabbabbbbbbabbababbbaabbbabbbbaabbabaabababab...
output:
YES
result:
ok single line: 'YES'
Test #17:
score: 0
Accepted
time: 29ms
memory: 35316kb
input:
bbabbabbbbbbbbabaabbbbaabaababbbababaabaababbbbbabbabbbbaaaaaaaaabbbaaabbaabaabbaaaaababbbababaabaaabbbabaaabbabbabaabbbaabbabaaaabbbbbabaaabbbabaabbbbaaaaabbaaaaabbaaabbbbaababbabbabbbbabbbaaaaaaabbaabbbbaabbaabbbbbabbaaababbbbaaababaaaabbaaaabbabbbbbbbabababaabababbbbabaaabbbaabbaabbaaabbbababbbab...
output:
YES
result:
ok single line: 'YES'
Test #18:
score: 0
Accepted
time: 29ms
memory: 34372kb
input:
bbbabaabaaabbabaaaaabbbbbbabbbbaaaaabababbabbabaaaaaabbbbaaabaabbababbbaaababbbbabababbabaababbbbabbbabbaaababbaabbbaaabaabbaabbbbabbbbbbbabbbbbabbbaabbbabaaaababbaaaabbbbbbabbaaabaaaabbbaabababaaaaaaabbbaaaabbbbbbbbabaabbaaaababaaaaaaaabaabbbabbabaababaabbaaababbbabababbbaaaabbaaabaabaabbbaabbbaabb...
output:
YES
result:
ok single line: 'YES'
Test #19:
score: 0
Accepted
time: 0ms
memory: 4672kb
input:
aababaabbabababbbabbaabbbbaaaabbababbbbbbabaaabaabbbaaabaabaababaabaabbaaabaaaabbabbbaaabaabbbbabbbbabbabaaabaaaabbaaababbbbaaabbbbabbabbbbbabbbbbbababbabbaababbbababababbbbbbbaabaabbabbaaabababaabaaabbaaaaaaabababbaaababaabbbaabaabbbabaaabbbbbaaabbabbabaabaabbbabbbabbabbbaabaaabbabbaabbbabaaabbbbab...
output:
NO
result:
ok single line: 'NO'
Test #20:
score: 0
Accepted
time: 5ms
memory: 4772kb
input:
abaabaabababaaaaaababaabbbbaabaaabbbabbbabaababbabbbaaaabababaababaababbabbabaabaaabababbbbabbbaaaaaabbaababbbbaabbbabbaabbbbbbabbabbabbaabbbabbabaabbaaaaaabbbbaaaaabababbabbabbbbabbabbababbbaabababaaaaababbbaaabaaabbabaababbaaabaabbaababbabaabaaaaaaabbbbabaabaabbaabbbbbbbbbbaaaaabbbbbbaaaaabbaaaaaa...
output:
NO
result:
ok single line: 'NO'
Test #21:
score: 0
Accepted
time: 5ms
memory: 4768kb
input:
babbaaaaaababaabbabbabaabbbaabbbbababbbbbaabbaaaaaaaabbaabaabbbabbbaaabbbabbbababbaaabbaaabbaabbababbababbaaaabbbabaaabbabaabaaabbababaaabbababbaaabaaaaaababaaababbaaabbbababbbbbbaabbabbaababbbbbbaabbaabbaaababaabbaababbbababababbbbbbaaaabbabbabaaabaabbababbabbaabaabbaabbbabababaabaabbabbbbbabbabaaa...
output:
NO
result:
ok single line: 'NO'
Test #22:
score: 0
Accepted
time: 7ms
memory: 5252kb
input:
babbabbbbbbbbbbbbbbbbbbabbaaabbaababbaaaaabbaabbaabbaaaaabbabaabababbbaaababaaabaaaabbbbbbbbbbbabaabbabbbababbbababbbaaabaaaaabbbabaababbabbbbabbbbbaabaaaababaabbbbaababbabbaabbbaaababaabaaaaaaaabbabababbaabbbbabbbbabababababbbabaabbbabaabbbbabaabbbbbbbabbaaaabbabaababbbbaabaaaabbabaaabaaaabbbbbbaaa...
output:
NO
result:
ok single line: 'NO'
Test #23:
score: 0
Accepted
time: 2ms
memory: 4080kb
input:
ababbbbbaabaababbbbababbbbaaaababbbaaaababbaaaaabbbabbaaaaabaaabbababbabbabbbbababbbbaabbbbbbbabaaaaaaaabbaaababbaabaaabaaabaaaabbaababaabbbbabbabbabbbbaaabbabbabababaaababbaabbbabbabbabbbbababbababaaaabbabbbabaabaaabbbaabbaaabbaabbaabbbaabaaaaabbabbbbaaaabaabaabababaabbbbaaabbbaabbaababbbabbaabbbbb...
output:
NO
result:
ok single line: 'NO'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
babbaabababbbabbabaaabaabaabbabaabaabaabbbbabbbabaaabbaabbbabbbbbbabaaabbaabaabbbabaaaaababaaaababaabaaaaabbbbaabbaaabbaabbaabaaababbaaaabbbbbaababaaaaaaababbbbbbbaaaababaaaaaaabababbbbbaaaababaabbbaaaabbbaaaaaaaaabbbbababbbbabbbbaabbbbabaabbbbbbbbaababababbabbbbabbbaaaaababbaaabbbbaabbaaaaaabbbaaba...
output:
CRASH
result:
ok single line: 'CRASH'