QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#440557 | #7262. String Modification | I_Love_Sonechka# | ML | 343ms | 484544kb | C++17 | 1.2kb | 2024-06-13 20:36:37 | 2024-06-13 20:36:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
const int inf = 1e9;
const int mod = 998244353;
bool debug = false;
const ld eps = 1e-9;
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
void solve() {
string s, t; cin >> s >> t;
int n = int(s.size()), m = int(t.size());
s = 'x' + s;
t = 'x' + t;
vt<vt<vt<int>>> dp(n+2, vt<vt<int>>(m+2, vt<int>(3, false)));
dp[1][1][0] = s[1] == t[1];
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
for(int k = 0; k < 2; ++k) {
dp[i+1][j+1][0] = dp[i+1][j+1][0] || dp[i][j][k] and s[i+1] == t[j+1];
dp[i][j+1][1] = dp[i][j+1][1] || dp[i][j][k] and (k == 1 || s[i] != t[j+1]);
}
}
}
cout << (dp.back().back()[0] + dp.back().back()[1] ? "Yes" : "No") << "\n";
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int tt = 1;
if(debug) {
tt = 1e5;
} else {
// cin >> tt;
}
for(int t = 0; t < tt; ++t) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
snuke snukent
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
snuke ssnuke
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 0ms
memory: 8184kb
input:
babaaaabaabbabbbbaaabaabbbbbbaaaababababbbbaabbaaaababababaaabaababbaaabbbbaabbbbbbbabaaabbaaaaabbbbabbabaabbbaaabaababbbabbaababbaaaababbaabbbaabbbababbbb baabbaababaaabababababbabbaabbbabbbbaaaabbabaababbababbaabbbaababaabbbabbbaabaabbababaababbaaabbaaababbaaaabbababababbbaaabbababababbbaaabbbabab...
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 4ms
memory: 8092kb
input:
babbbaabbababaababaabaaaabaaabbbbabaabaaabaaaabaabbabbbababaababaaabbbaaabbbbaabbbaababbbbaaababaaabaaaaaaabaabbbbaaaabbabbbaabbaaaabbbbabbbbaaaabaaabbbaaa bbbaabaabbbababbbbabbabbababaaaabbabbaababababbabbaababbaaabaaaabbaaababaabaabaaabbbbabaabbabbaaaabaaabaaaaabbaaabaabbaabaaabbbabbbbbaaabaaaabbb...
output:
No
result:
ok answer is NO
Test #5:
score: 0
Accepted
time: 5ms
memory: 8136kb
input:
aabbbabbbaabbbaabbabaababbbabbbbabbaaababbabbaaabababaabaaabbbaaaabbaaaabbaaababaababbbbbbbaaaababaaabbaabbbaababbabbaaabaaababbbaabbbabaabbaaababbaaabaabb abaaababbabbbabbaabaabbbaabaaaababbabbabbbbbabbaaaaaabaabbbbbbbbabbbbbabbbbbbbbabaaaabaababbbabbbbababaababbaabbaabbabaaabaabaabaabbabbaaabbabaa...
output:
Yes
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 4ms
memory: 8312kb
input:
abababbaababaaaababbaaaaabbbbbbbbbbabababbbbbbbabbaabbabaabaaaabbbaababbbbabaababbabbabbbaaabbaaababbaaaaababbbaaaabaabaaaabaabbbbbaaaaaaaabaaababaabbbaaaa abaaababababaababbababbaabaababaaabababaaababbbaaabaaaabbaababababaaaabababababbabbabbababababbbababaabbbabaabababbabbabbababababababababbabaabb...
output:
Yes
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 0ms
memory: 8360kb
input:
aabbababababbbaaaaaabbaababbbbaaaaabaabaabaabbbabaaabaabaababbbabababbababababbbbabaaabaabbabaabbababbaaaabbaaaaabaabaabbbbaaabbbbaaaabababbaaaababbbbaaaba aaaabbaabbbbbaaabbaabaabbababbabbaabaaabbbababbbbbaaaaabaaabbbaaaabbbaaababaabbabaabbaaaabbbbbbabaababbaabbbababaabbbbbababbbbaaabbbbaabaaabaaba...
output:
No
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 2ms
memory: 8204kb
input:
aabababbaaaaabaabaabbabbabbaabbaabaaabbaaabaaabbbbbaaaabaabbaaaabbaabaaaaabaabbabababbbabababaabbaabbbbabbabbababaaaabaaababbaaaababbababbbabbabababbabbaaa abbaabbaababbbabbaaabaaababbabbbbababbaabbbbabaaabbabaababbaabbaaaabbaaabaababaabbaabbbbaaabbbbabaabaaaaaaaaabbaaaaabbbaaababbbbbbabbabbaabbbbba...
output:
Yes
result:
ok answer is YES
Test #9:
score: 0
Accepted
time: 4ms
memory: 8128kb
input:
bbbaaaaaaaabaabbabaabaaabbabbbbabbababbbbbaaabaaaaababbbaaaababbbabbababbabbbbabbbaabbaabbabbaabbabababaaabbaaabababaaabaaabababababbbaaababbbbaaaabbabbbba bababbbabbaabbaababaabbabababbaabaaaabbbaabbaaabbabbaababbaabaaabaabaaabbbaabbabbabbababbababbabbabaaababababbaabaabbababbababababaabaabbabababa...
output:
Yes
result:
ok answer is YES
Test #10:
score: 0
Accepted
time: 4ms
memory: 8212kb
input:
abaaaaaaabbaabbbbbababbbbbaabababbbaaababbbaaaaabbbaabaabababbaababbabbabbaababbbbbabbbabaaabbbabababbaaaaaaaabbaaababaabbaaaabababababaaaaababbabaabbaabab abaabaaaabbaaaaabbbabaaabababbbaabaaaaabbbbabbbbabaaaabbbbaaabaabbbabbbbbbbbabbbbbbababbbaabbabaaabbbaaaaaababbabaaabbbabbabbbabaaabbabbbaaaaabb...
output:
Yes
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 4ms
memory: 8152kb
input:
ababaaaaaabbaabbbaaabbbaaaabaaabbaaabbaabaabbbbbbbbbabaabbaaaaaabbbbabbbabbbbabbbbababaaaabaaabbaabbbaabbaababbababbaabaaabbaaaaabbabbbbabbaaaababababbbabb abbababaaabaaaabaabaaaabbaabaaababababaaababababbbbaaabababaaaabbbbbbbbbbbbabbababbbbaaabababbbbbbaaaabababbabbbaabbbabbbabbbbbbbbbbabaabaabaaab...
output:
Yes
result:
ok answer is YES
Test #12:
score: 0
Accepted
time: 318ms
memory: 484544kb
input:
bbbbaaaaaababababbabaabbaababbabbbababbabaabbabbabbaabbbaabbbaababbaaabaabbbbabbaabbbbbababababbbbbbaaaaabbbbabbbabaabbaaababababbabbbbabbabbbabaaabaaabaabaaabaaaaaaabbaabbbbabaababababaabbabababbbbabaaaaabbabababbbaaabaabbabaaaaaabbbabaaabbbbbbaabbbbababaabababaabaabaaabbabaaaababbabbbaabbbaabababa...
output:
Yes
result:
ok answer is YES
Test #13:
score: 0
Accepted
time: 324ms
memory: 484452kb
input:
aaaaabbbbaaaabbabbbababbaaaabbabbbbbbaaabaabbabbaaaaaaabababbabbababbaabbbbbabaaabaababbbbababbaaabbbbbbabaabbbbaaabbbbaabbbbaabbbbaabbababbaaaaaabaababaabaabaabababbbabbabbbbbbabbbaabbaabbbaaababbaaabaaaaababaaababbaabababbbaaabaababbabbbbaabbaaabbababbbbbbbbbbbbbaaabaabbbaaababaaabbbabbabaaaababab...
output:
Yes
result:
ok answer is YES
Test #14:
score: 0
Accepted
time: 304ms
memory: 484420kb
input:
babababaaaabbaabbbbababababbbabbabaabbbaaaabbaaaaaaababbbaabbbbbaaaabaababbaaabbbabbabaaabaabbabaabbbbabaabbaaabbaaababaaaaaabababbbabaaaabbabbaabbbbabbbabbabbaaababbabbaaabbbbabbaabababaabbaabbbbbbabaaaabaabaabbabbbabbaaaabbabaabbababaabbabbbaabbababaabbabbbbabababababaabbbbabaaabaababaaababbbbabab...
output:
No
result:
ok answer is NO
Test #15:
score: 0
Accepted
time: 310ms
memory: 484444kb
input:
abbbbabbaaaabbbbabaabaaaababbaaabbbaaabbabbbaaabbbabbaaaaabaabbbaabbaabaabbabaaabaababaabaabbaaaabbbbabbabababbabbababababaaabaabbaaaabaaababaabaaaabaaaabbbbabbbabbabbbaaabaaaabbbabbaabbbbababaaaabbbbabbabbbabbbbbbaababaaaabbabbbbabbbababbbbabaaaabbaaababbbbaababbbbbbabbabbaaaabbabaaabbaabbbaaabbaaa...
output:
Yes
result:
ok answer is YES
Test #16:
score: 0
Accepted
time: 290ms
memory: 484388kb
input:
babaaabbabaaabbaaabababbbabaaabbaaababbbaaababbaabbbabbbbbabbbabbbabbbbabaaaaaaabaababbaaabababaaaaabbbbbbbaaaaaaaabbababbabaaaaaabbbbbbaabaaabaaabababababbbbbaabbbabaabaaaabbbaaabbabbabbabbbabbaaabbbbbbaabbbbaaaaaabbaababbaaabaabbbababaaababbaaaaabaaaaaababaaabbaabaabaaababbbaabababaabaabbaabaaaaab...
output:
Yes
result:
ok answer is YES
Test #17:
score: 0
Accepted
time: 288ms
memory: 484424kb
input:
babaaaaaabbaabaaabaaabbabbbbbbbababbaaababababbbaabaababaabbbabbabababbabbbbbbaaabbabbabababbbabbbababaaaabbbaaabbaaabbbbabaaabaabaaaaabaaabbabbbaaaaaaabaababbbbabaabbabaabbaabbaaabaaabbbabbabbaababaaababaaabaabbbabbaaababaaabbababbbbbbbabaabbbbbbaabbbababbbaabaabaabbbababbababbaaaaabbbabbabbaaaabaa...
output:
No
result:
ok answer is NO
Test #18:
score: 0
Accepted
time: 334ms
memory: 484316kb
input:
abaaabbaabbbaabbbbbbbabbabaabababaaaabaabbaaabbabaaabaabaaaaabaaabbabbaaabaaaabaaabababbaabaabbbbbbabbababaaababbaaaaaaaaababaaaaabbbbbabbbbaaababbaaabaaabaabbabaababbbabbbaababbaaababaaaaabbbaaababaaabbaaaabbabbbbaaababbaabbbaaabbbbbabaaabbbbababbaabbbabbbbaaaababaabbababbbbabaabbaababaababababbaba...
output:
Yes
result:
ok answer is YES
Test #19:
score: 0
Accepted
time: 343ms
memory: 484416kb
input:
babbbaabbbbabbabaaaabbbababababbabbaaaabaabaaaabbbabbbaaabbaababaaaabbaabbabbbababbbaaababbbaaabaaaaaaaaababaabbabaaaabbbaababaaaabbbaaaaaababbbaaaaabaaabaaabbaaabbbbbbbaaaaaabaabababbabbbbbbbaababbaaaaaababaaabbbaabbaaaabaaababaabbabababbbbabbabaaababaaaaababbbaabbaaaaaaaaababaabbbaaaabbbbabbaabaaa...
output:
Yes
result:
ok answer is YES
Test #20:
score: 0
Accepted
time: 295ms
memory: 484472kb
input:
aabbbabbbabababbabbbbabaabbbabbabbbabaaabbaababbabaabababbaaaabbabaabababbbbabaabbbbbbbaaaabbbbababababbaaababaabaaabbabbbababababaababaaaabbbabaabbbbababaabbaaabbaaabababbbababbaababbaaaabaabbaabbabbababbbbababbaabbbbbabbbaaababaababbbaabbaabbabbbbbaabbbbbaabbbbbbaababbbabbaaaabbababbababaaababbbbb...
output:
No
result:
ok answer is NO
Test #21:
score: 0
Accepted
time: 36ms
memory: 65608kb
input:
rjpasogyjvbvvoktzfxbubmoycqgngssowfkszviaqvjmcephxfbuowkjniqeqadlqjotalrnpfzricoivfnuqxkcccnxvowexhhosrhubzdyhxedxjjnatmrbenwnuomtdvrxgnhuopydydddvxwvzjpmktjlrdedkpeumyesptcmvgedxqnnsohafwlorhcvhrtjguqoqfegkgebcsgouhbxfksqisyzchowltjdxzwqkbnrsmabzalehtebpxxnlozehchvrglxtxcczzubwnafykgmpxkjdjdoazruxs...
output:
Yes
result:
ok answer is YES
Test #22:
score: 0
Accepted
time: 48ms
memory: 65396kb
input:
oddoybpchccvijeqmtjyipytwfnebyntyvtpvejxxowwkbqlpevtzchzdxorfoafemqvyjwzjqlapflaacnjtwaambhacyhbeviigsrpxifmdtxapdpbrzdmjtmqiwzzppkydeegxtmcxlnnekmwfkimwrzppmptvgyexnziaoaaypuaufkwtglfzyxoaedyleixooeexjkpxtaznmarglrfpcvlegrpwijblhpkkejkyyjtkplsxteisungdqayubuwzmcuhpvjftczzknoglujdvnlutejdhokuzmmtijg...
output:
Yes
result:
ok answer is YES
Test #23:
score: 0
Accepted
time: 30ms
memory: 65436kb
input:
xuydwbcmtlayumrmsiuueutqhonbkvywecdorvgsqobcovenbvbdaodzcvsmryttmwgpujzonvsdogpdykordfxuotbbxziikuyihjisixjodjwoefwwpzebbhotjxdtsulbunyqmagqtyavwmafxspumnqnpswyweorymfnrordzzynmidfzdflsvirdwyxkevlwovfqmrpzntuuwqkjrepvasnlehkcjqdmfxledwcpauuputevamycxgcrpmyizidyqvybvjntpagaaakzgvmblbirjaljbwshipixayj...
output:
No
result:
ok answer is NO
Test #24:
score: 0
Accepted
time: 32ms
memory: 65488kb
input:
unsxzpjewyirblkzgusgtkgmtyyyuposeiwgthbqhsmijougetqlujltwlcnmfnwaaqihofkdlebctbkteneipincvhwlmyxdqioflenlcwqrbtmemvyjondlxnfvjbpxsiwqtlvmwmvhymqbcnralxaadvghigaiowgbggrqidmqyesweqqwpdmqvtnmoiqhhmtyooyscvxkuitniqlfekwtkhfyawwxsaankxahknwulvymdwekodqjtprzdkxcerbndlvdragvpnbvvclfhvczijtkqatzjxyfzfeyzoh...
output:
Yes
result:
ok answer is YES
Test #25:
score: 0
Accepted
time: 28ms
memory: 65440kb
input:
wsqeywynfwqjynejgdommykqnebbszcifsenlkgtjlkhodrshlsdmwhfuhvktijpxdebjvygzyvociioivrprknkrpnfuvydfbktnwupiuhlpqbwaveixdaggiqzhjjurcdqqxudkjjdhljaeivgtyksprqvqqikdlsmocvohhykbcrwcwykwykivdnvyskpxlntrpxufdkedcvhmlfriirwemktcmrgtmwqeeztbwrjjnbatgakhnlxsxeyihoafubkgdoyyozayinbaothgadiqplsgpuvurgnxxqqhpfs...
output:
Yes
result:
ok answer is YES
Test #26:
score: 0
Accepted
time: 36ms
memory: 65436kb
input:
noacdjquzfvdhpmishqcduvxdxegpgyunnpshsfjqctcrkfwviuoxslpznxqksbhzailaghqdoyrvprwoeeipxdyjjmrtdqbxjdgqajrahluokuhtubdrbhivzqvwgbftvkcsknivjqxrnxvyjgwgsjshkbljtxhdumzhqmwnlpqkkxdcxxfpplibqesikbsdlbrhwcevmfnwvmuhcuybxtmuqdmrnxlodsbwmlkucemteysmigwymiqrsccwwfowyfnxaewwzxmzaldcamoicokqussudabzymdxlsvvyjw...
output:
No
result:
ok answer is NO
Test #27:
score: 0
Accepted
time: 32ms
memory: 65680kb
input:
hhetrzeyrtvinztqqszhgppllyzzuyrfvtcziiunmtzyjmjcsoyqlifcjpepfjvwqsdxghogskyvqxihkxxskkssggmunjjxzfmfsbmxmifkbvuclrkjgivkkmdifemfifrqudoqtiidvwwcllyyabriduitthofdmcgizqwxxmueiezobqnqbkkweyettbnpcycsdkwkxedliapnrkxylohcsvugcsnskxmssrexpjqbnhgdpsxprgptzndljychdmaawhcnpwxavunwpdayfexizgccwdwrnbnvcixibyn...
output:
Yes
result:
ok answer is YES
Test #28:
score: 0
Accepted
time: 36ms
memory: 65436kb
input:
ztjxpjjnbldssbglkmncptynicwspotxrgmertzalkiattjwbowxivnvcrdrbaygwuibazqzlfihrlgtqdugbzwocxlwjsgpzuyzdviczkdieaijgiagbjajyrwglayaatpfqglrdmebylfzvrstubbqxskelfkodpznbbicreevgjarccqpfmhxsgakdtbtymhxzaoxyvkidvljwutwwwebrtlsbhujdhumqrfcwlqkdgkghvwhxdjtkodvrqwbqhonjztumwuaipygncfnfohodtrlceqqagxqvinbuobz...
output:
Yes
result:
ok answer is YES
Test #29:
score: 0
Accepted
time: 32ms
memory: 65428kb
input:
dgppwjunfsuzqlqdevvzbiapopczqikjlfsimjwcytoblxewkxmkjjvxqyulszzgpnlrwoycbnpnqjineztlgafzzuounxxazhtyxmapburkglfntgardqklapjberdyrcilkfoxcvrknybocdvyzifjgphbadmvwgzcoutpqlcwksjomlwavjdprruktxchcvnowhktegiveylocgtmaasvtvpupelkssqtwumyfopntrrlniwfbfezsrxwhjgghosndrqpbymqrljdcphhatxypdyrwnmulhddnebbuvpe...
output:
No
result:
ok answer is NO
Test #30:
score: -100
Memory Limit Exceeded
input:
lyajbptvgbpzebanuelrgazkpxwfmybqxgntcsxvynmcfcvztctuulwbxosffwpxclbofshgmormuehvvtmxvrvqcjbxtgpshsbtiuudkcmlniecabenxbgcrhqatltdgxhodxrkdxxnczpbqqzejhjfdehwcqfvjelbdxobnmkrptdmskqjhtusgwabyptmiukhbxxhtwxyqggznwylgeljmpyupuvdrfvpghtmebcmornzphdkffcstaeiafmuuexdftflizyglkydejpitcwuquybogrzumcpdjprhvdy...
output:
Yes