QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64063 | #2487. Check the String | As3b_team_f_masr# | AC ✓ | 49ms | 62000kb | C++ | 5.5kb | 2022-11-24 01:04:46 | 2022-11-24 01:04:49 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'