QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#64063#2487. Check the StringAs3b_team_f_masr#AC ✓49ms62000kbC++5.5kb2022-11-24 01:04:462022-11-24 01:04:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-24 01:04:49]
  • 评测
  • 测评结果:AC
  • 用时:49ms
  • 内存:62000kb
  • [2022-11-24 01:04:46]
  • 提交

answer

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, -1, 0, 1, -1, 1};
int dj[] = {1, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 998244353;
const int N = 1e5 + 5, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int t, n, par[N], p[N];
string req, tmp[N];
vector<deque<char> > s;

int find_set1(int node) {
    if (par[node] == node) return node;
    return par[node] = find_set1(par[node]);
}

int find_set2(int node) {
    if (p[node] == node) return node;
    return p[node] = find_set2(p[node]);
}

void mrg(int me, int one, int two) {
    one = find_set2(one), two = find_set2(two);
    deque<char> c;
    if (one == two) {
        for (int i = 0; i < s[two].size(); i++) c.push_back(s[two][i]);
        for (int i = 0; i < c.size(); i++) s[one].push_back(c[i]);
        while (!s[two].empty()) s[two].pop_back();
        p[me] = one;
    } else if (s[one].size() < s[two].size()) {
        for (int i = s[one].size() - 1; i >= 0; i--) s[two].push_front(s[one][i]);
        while (!s[one].empty()) s[one].pop_back();
        p[me] = two;
    } else {
        for (int i = 0; i < s[two].size(); i++) s[one].push_back(s[two][i]);
        while (!s[two].empty()) s[two].pop_back();
        p[me] = one;
    }
}

//#define endl '\n'
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("farm.in", "r", stdin);
    //memset(dp, -1, sizeof dp);
    deque<char> nogoal;
    s.push_back(nogoal);
    s.push_back(nogoal);
    s.push_back(nogoal);
    for (int i = 1; i < N; i++) par[i] = p[i] = i;
    s[1].push_front('a'), s[2].push_front('b');
    stack<pair<int, int>> sz;
    sz.push({1, 1});
    sz.push({2, 1});
    cin >> req >> n;
    int id = 2;
    for (int i = 0; i < n; i++) cin >> tmp[i];
    for (int i = 0; i < n; i++) {
        if (tmp[i] == "copy") {
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            int idnew = ++id;
            int sznew = sz1;
            par[id1] = idnew;
            s.push_back(nogoal);
            sz.push({idnew, sznew});
        } else if (tmp[i] == "swap" && sz.size() >= 2) {
            int sz2 = sz.top().second;
            int id2 = sz.top().first;
            sz.pop();
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            sz.pop();
            sz.push({id2, sz2});
            sz.push({id1, sz1});
        } else if (tmp[i] == "roll" && sz.size() >= 3) {
            int sz3 = sz.top().second;
            int id3 = sz.top().first;
            sz.pop();
            int sz2 = sz.top().second;
            int id2 = sz.top().first;
            sz.pop();
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            sz.pop();
            sz.push({id2, sz2});
            sz.push({id3, sz3});
            sz.push({id1, sz1});
        } else if (tmp[i] == "fuse" && sz.size() >= 2) {
            int sz2 = sz.top().second;
            int id2 = sz.top().first;
            sz.pop();
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            sz.pop();
            int idnew = ++id;
            int sznew = min(1000000000, sz1 + sz2);
            par[id1] = par[id2] = idnew;
            s.push_back(nogoal);
            sz.push({idnew, sznew});
        } else return !(cout << "CRASH");
    }
    if (sz.top().second != req.length()) return !(cout << "NO");
    while (!sz.empty()) sz.pop();
    id = 2;
    sz.push({1, 1});
    sz.push({2, 1});
    for (int i = 0; i < n; i++) {
        if (tmp[i] == "copy") {
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            int idnew = ++id;
            int sznew = sz1;
            s[idnew] = s[find_set2(id1)];
            sz.push({idnew, sznew});
        } else if (tmp[i] == "swap" && sz.size() >= 2) {
            int sz2 = sz.top().second;
            int id2 = sz.top().first;
            sz.pop();
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            sz.pop();
            sz.push({id2, sz2});
            sz.push({id1, sz1});
        } else if (tmp[i] == "roll" && sz.size() >= 3) {
            int sz3 = sz.top().second;
            int id3 = sz.top().first;
            sz.pop();
            int sz2 = sz.top().second;
            int id2 = sz.top().first;
            sz.pop();
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            sz.pop();
            sz.push({id2, sz2});
            sz.push({id3, sz3});
            sz.push({id1, sz1});
        } else if (tmp[i] == "fuse" && sz.size() >= 2) {
            int sz2 = sz.top().second;
            int id2 = sz.top().first;
            sz.pop();
            int sz1 = sz.top().second;
            int id1 = sz.top().first;
            sz.pop();
            int idnew = ++id;
            int sznew = min(1000000000, sz1 + sz2);
            mrg(idnew, id1, id2);
            sz.push({idnew, sznew});
        } else return !(cout << "CRASH");
    }
    string ans = "";
    int me = find_set2(sz.top().first);
    for (int i = 0; i < s[me].size(); i++) ans.push_back(s[me][i]);
    if (req == ans) cout << "YES";
    else cout << "NO";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7408kb

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: 4ms
memory: 7240kb

input:

a
0

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 4ms
memory: 7272kb

input:

aaba
1
roll

output:

CRASH

result:

ok single line: 'CRASH'

Test #4:

score: 0
Accepted
time: 0ms
memory: 7340kb

input:

abbabaaaababbabaaaaaaaabaababbbbbbabbbbabbbabbaabbababaaaaaaaabaababbaabbabbabaabaabbbabbbbabaabbabbbbabaaaaabbbaabaabaabbabbaaaababaaabbbbbbabaabbababbbabbbbbbbababbabbbbaaaaaaabbbbabaaabbabbababababaaabaaaaaaababaabbbabbbabbaabbbabbbabbbbaabaaabbaaabbbbbaabbbaabaabbbbbaaaabaaabbaabaaaaaabaababaaaa...

output:

CRASH

result:

ok single line: 'CRASH'

Test #5:

score: 0
Accepted
time: 2ms
memory: 7452kb

input:

abbabaababbabbbabbbbabaaababbbbbbbabbbbbaabaababbbbababbaabbaabaababababbababbbabababaabaaabbabbbbbabaaaabaaaaaaaaaaabbabbbababbbbbabbbbbbaaaaabaaabbbaababbabbaabaabbbaabbaabbbbababaabaaaabbabbbaabbbbabbbababbaabbaaabaaaabbbabbbbaabababbbabbaababaaaaaabbbaaaabbabbbaaabbabaaaaabbaabbabbbbbbabbabbaaba...

output:

CRASH

result:

ok single line: 'CRASH'

Test #6:

score: 0
Accepted
time: 5ms
memory: 7368kb

input:

baabbbbabababbabbaababaaabbbbabaabbbbbbbaaabbbabababbaaabbabbbbbbabaaabbbbbaababbaabababbbbbaaabbbababaaaaabaabbaaababbaaabbbbbbbabaaaaabaabbabaaabbbabbbbaaaabaaabbbabaabbaabbbbaabaaabaaababbaababbabbbaabbaaaaabababbabbbbbaaabbbbabbaabbbbaaababbbbbbaaabaaabbabbbaaaabbbabbbabbbabaaaaaaabbbbabaabbbbaa...

output:

CRASH

result:

ok single line: 'CRASH'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7472kb

input:

babbbbaaaaaabbbaaabaaababaaababbbaabaaaababaaaaababbbbaabaababbababbababbbbbabaaabbaabbbaabbbaabbbaaaabaaaaaabbbabaabbaaaaababbbbbbbbbaaaabbbbaaaabababaaababaaaabbbaaaaaaababaabaabbbabbbabababbabbbabbabaaabaabaaaabaaabaababababababbbbbbbbabbaaabbbbbaabbbbabbbbbabbbabaabaaaaaaaabbbbbbbbbaabababaabbbb...

output:

CRASH

result:

ok single line: 'CRASH'

Test #8:

score: 0
Accepted
time: 10ms
memory: 7452kb

input:

abbaaabbbababbaaaaaaabaabbbbababababaaaabbbbbbbbbaabbbbbabbbaabbabbbbaaabababaaababaabaabaababbbaabaaabbabaaaaaaaababbaabaaaaabaabaabbbbababbbabaaaaababababbaababbaabbbbbbbbbbbbbaabaaaabbbaaaaaabbbbaaaabbbaaabbabbaababababaabaaabababababaabbbbbbbababbabbabbbaaabaaabbaaabbbaaaababbbabbbababbbbabbaabb...

output:

CRASH

result:

ok single line: 'CRASH'

Test #9:

score: 0
Accepted
time: 8ms
memory: 10392kb

input:

aaaabbbbbbbababbbbaaaaabbaaababaabbaaabaaabbbbabbbabbbabaababbbaabaaaaaabbbbabaabbaaabbabaabaabaabbbabbbbbaababababababbabbbbbaabbbababbbbbabbbbabbaaababaabbbaaaabbaaabbbbaaabbaabbbabbaaababbaaaabaabaababbabbabbbaabbbaaabaaaabbaabbabbabbbbbbababbbaaaabbabbaaabbaaaababbbaabaababbbbabbbababbababbbabab...

output:

CRASH

result:

ok single line: 'CRASH'

Test #10:

score: 0
Accepted
time: 6ms
memory: 24532kb

input:

aabbabbababaabbbbabbbbaaaaaabbbbabbaabaabbaaabaabbabaabbabbbbbabbbbabbbabababbbaaaaaabababbaaabbbabababbbbbbabbbabbaaababbabbaaabbaaaababababaababbababbbaaabaabbbbaaaabaaababbbbabbbaabababbbbaabbaaabbabbbbaaabbbabbbbabaaaababbbbababbbbababbaababaaabbabbbbbabbabbaabbbabababbabbbaabbaaaaabbaabbbbaaabb...

output:

NO

result:

ok single line: 'NO'

Test #11:

score: 0
Accepted
time: 13ms
memory: 24128kb

input:

abababbaabbabbbbabbbaaabababbbababaaababaabaaabbaaabaaabababbbbbbaaaaaabbbbabbbbabbaaabbbabababbbaababbbabbaaababbbbbbbbbbbbaabaabaaabbabbbaaaabaaaabbbbababbbaabaabaaaaabbbbbaaaaaabbbaabaaabbaaabbbabbbbbbaaababababaabaabbbbbbabaababaaabaaaabaaabbabaabbbbbaaababbabaaaabbaaababbabbbaaababbbbbbbbbaaabb...

output:

YES

result:

ok single line: 'YES'

Test #12:

score: 0
Accepted
time: 19ms
memory: 21812kb

input:

aabbaaabaaaaaabaaaaabaabbbabaabbaaaabbaaababbbbbbbaabbababbbbaabaaabaaabbababbaaaabbabaaaaaaaaaababbababbaaaaababbabbbbaaabbbabaaaabababbbbabababbbaabaabbbbabababaabababbabbaaaabaaabaabbaaabbbaabbbbbabbbaabbabaaaaaaababbaabaaaaabbaabbbababaabbaababababababaaabbbbbababababbbaabaaaabbaaabaabaabababaaa...

output:

YES

result:

ok single line: 'YES'

Test #13:

score: 0
Accepted
time: 9ms
memory: 23888kb

input:

abaabbabbbababaaababbababababbbabaaabaaabbaaaabbbaabbabaabbaabaabaaabbaaaababaabaaababaaabbbbabaaabbbaaaaaaaaabbabaabbbabbaaabababbbbaabbababaaabaabababbabbabbbababbbabaabaaabaaaaabaaaabbabbbbababaaababbbbbabaaaabaaabababbbaabbbaababbabaaabbbabaaaaaabaabbaaaaabaaabaabbbbbaaabaaaaaabbbaaabbababaabbba...

output:

YES

result:

ok single line: 'YES'

Test #14:

score: 0
Accepted
time: 13ms
memory: 18628kb

input:

aabbbbbaabababbabbbaabababbabbabbbabbbbaababbaaabbabababaaabbaabaaaabbbbbbbbbaaabbbbbaaaababaaabbabbaaaababababbabaabaaabaaabbbbbbbbababababbaabaabbaaaaaababbaaaaabbaaaababbabaabbaaabaabbbabaaabaaaababbbbbababaabbbaabaabbaabbbbabbaabaaaabbaabaaabaabababaaaaabbabbbbabbbbbbabababbabbabbbaabbabaababbaa...

output:

YES

result:

ok single line: 'YES'

Test #15:

score: 0
Accepted
time: 4ms
memory: 16964kb

input:

bbaabbabbbbaabababbbbaabbbababbbabbbbabababaaabbbbaaabaabbabaaabaaaabaabababbbbaaababaaaaababbaabbbbbbabbbabbbbbabbabbabaabbbbbbbabbbaaaaaaabbabbabbbbbaaaabbabbbaaaaaaababbbabababaaababbbabbabbaaababaabaaaabbabbababbabababaabbaabbbaabbaaabababaabaaaaaaaabaababbbabaababaaabaaaabbaabaababbbabababaabba...

output:

YES

result:

ok single line: 'YES'

Test #16:

score: 0
Accepted
time: 45ms
memory: 58244kb

input:

aaabbabbbabbbababbbaababaabbbaaabbaaabbabbbbaabaabbabababbbbbaabbaaaabbbaaabababbabbaaabaaaabaaaaabbbbbbaaaaaabababbbabaabbabaaabaaababaaabbbbaaabbaabbbababbbbabbaaabababbabaabaabababaababaabbbaaababaababaaababaababaaababaabbabaaaabbbbabbbabbaababbbbbbbbbaabbabbbbbbabbababbbaabbbabbbbaabbabaabababab...

output:

YES

result:

ok single line: 'YES'

Test #17:

score: 0
Accepted
time: 39ms
memory: 62000kb

input:

bbabbabbbbbbbbabaabbbbaabaababbbababaabaababbbbbabbabbbbaaaaaaaaabbbaaabbaabaabbaaaaababbbababaabaaabbbabaaabbabbabaabbbaabbabaaaabbbbbabaaabbbabaabbbbaaaaabbaaaaabbaaabbbbaababbabbabbbbabbbaaaaaaabbaabbbbaabbaabbbbbabbaaababbbbaaababaaaabbaaaabbabbbbbbbabababaabababbbbabaaabbbaabbaabbaaabbbababbbab...

output:

YES

result:

ok single line: 'YES'

Test #18:

score: 0
Accepted
time: 49ms
memory: 59996kb

input:

bbbabaabaaabbabaaaaabbbbbbabbbbaaaaabababbabbabaaaaaabbbbaaabaabbababbbaaababbbbabababbabaababbbbabbbabbaaababbaabbbaaabaabbaabbbbabbbbbbbabbbbbabbbaabbbabaaaababbaaaabbbbbbabbaaabaaaabbbaabababaaaaaaabbbaaaabbbbbbbbabaabbaaaababaaaaaaaabaabbbabbabaababaabbaaababbbabababbbaaaabbaaabaabaabbbaabbbaabb...

output:

YES

result:

ok single line: 'YES'

Test #19:

score: 0
Accepted
time: 16ms
memory: 28888kb

input:

aababaabbabababbbabbaabbbbaaaabbababbbbbbabaaabaabbbaaabaabaababaabaabbaaabaaaabbabbbaaabaabbbbabbbbabbabaaabaaaabbaaababbbbaaabbbbabbabbbbbabbbbbbababbabbaababbbababababbbbbbbaabaabbabbaaabababaabaaabbaaaaaaabababbaaababaabbbaabaabbbabaaabbbbbaaabbabbabaabaabbbabbbabbabbbaabaaabbabbaabbbabaaabbbbab...

output:

NO

result:

ok single line: 'NO'

Test #20:

score: 0
Accepted
time: 21ms
memory: 31616kb

input:

abaabaabababaaaaaababaabbbbaabaaabbbabbbabaababbabbbaaaabababaababaababbabbabaabaaabababbbbabbbaaaaaabbaababbbbaabbbabbaabbbbbbabbabbabbaabbbabbabaabbaaaaaabbbbaaaaabababbabbabbbbabbabbababbbaabababaaaaababbbaaabaaabbabaababbaaabaabbaababbabaabaaaaaaabbbbabaabaabbaabbbbbbbbbbaaaaabbbbbbaaaaabbaaaaaa...

output:

NO

result:

ok single line: 'NO'

Test #21:

score: 0
Accepted
time: 19ms
memory: 31548kb

input:

babbaaaaaababaabbabbabaabbbaabbbbababbbbbaabbaaaaaaaabbaabaabbbabbbaaabbbabbbababbaaabbaaabbaabbababbababbaaaabbbabaaabbabaabaaabbababaaabbababbaaabaaaaaababaaababbaaabbbababbbbbbaabbabbaababbbbbbaabbaabbaaababaabbaababbbababababbbbbbaaaabbabbabaaabaabbababbabbaabaabbaabbbabababaabaabbabbbbbabbabaaa...

output:

NO

result:

ok single line: 'NO'

Test #22:

score: 0
Accepted
time: 34ms
memory: 36680kb

input:

babbabbbbbbbbbbbbbbbbbbabbaaabbaababbaaaaabbaabbaabbaaaaabbabaabababbbaaababaaabaaaabbbbbbbbbbbabaabbabbbababbbababbbaaabaaaaabbbabaababbabbbbabbbbbaabaaaababaabbbbaababbabbaabbbaaababaabaaaaaaaabbabababbaabbbbabbbbabababababbbabaabbbabaabbbbabaabbbbbbbabbaaaabbabaababbbbaabaaaabbabaaabaaaabbbbbbaaa...

output:

NO

result:

ok single line: 'NO'

Test #23:

score: 0
Accepted
time: 6ms
memory: 14624kb

input:

ababbbbbaabaababbbbababbbbaaaababbbaaaababbaaaaabbbabbaaaaabaaabbababbabbabbbbababbbbaabbbbbbbabaaaaaaaabbaaababbaabaaabaaabaaaabbaababaabbbbabbabbabbbbaaabbabbabababaaababbaabbbabbabbabbbbababbababaaaabbabbbabaabaaabbbaabbaaabbaabbaabbbaabaaaaabbabbbbaaaabaabaabababaabbbbaaabbbaabbaababbbabbaabbbbb...

output:

NO

result:

ok single line: 'NO'

Test #24:

score: 0
Accepted
time: 0ms
memory: 7408kb

input:

babbaabababbbabbabaaabaabaabbabaabaabaabbbbabbbabaaabbaabbbabbbbbbabaaabbaabaabbbabaaaaababaaaababaabaaaaabbbbaabbaaabbaabbaabaaababbaaaabbbbbaababaaaaaaababbbbbbbaaaababaaaaaaabababbbbbaaaababaabbbaaaabbbaaaaaaaaabbbbababbbbabbbbaabbbbabaabbbbbbbbaababababbabbbbabbbaaaaababbaaabbbbaabbaaaaaabbbaaba...

output:

CRASH

result:

ok single line: 'CRASH'