QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#65451#2487. Check the StringThree_Sannin#AC ✓17ms4724kbC++142.6kb2022-11-30 21:28:092022-11-30 21:28:12

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-30 21:28:12]
  • Judged
  • Verdict: AC
  • Time: 17ms
  • Memory: 4724kb
  • [2022-11-30 21:28:09]
  • Submitted

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'