QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#395111#2487. Check the StringMassachusetts Institute of Terriers (Yi Du, Mutiraj Laksanawisit)#AC ✓29ms35316kbC++203.4kb2024-04-21 04:44:502024-04-21 04:44:50

Judging History

This is the latest submission verdict.

  • [2024-04-21 04:44:50]
  • Judged
  • Verdict: AC
  • Time: 29ms
  • Memory: 35316kb
  • [2024-04-21 04:44:50]
  • Submitted

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'