QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#440557#7262. String ModificationI_Love_Sonechka#ML 343ms484544kbC++171.2kb2024-06-13 20:36:372024-06-13 20:36:38

Judging History

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

  • [2024-06-13 20:36:38]
  • 评测
  • 测评结果:ML
  • 用时:343ms
  • 内存:484544kb
  • [2024-06-13 20:36:37]
  • 提交

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

result: