QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440563#7262. String ModificationI_Love_Sonechka#WA 1ms4036kbC++171.3kb2024-06-13 20:42:372024-06-13 20:42:41

Judging History

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

  • [2024-06-13 20:42:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4036kb
  • [2024-06-13 20:42: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());

const int maxn = 5010;
bitset<maxn*maxn*2> dp;

void solve() {
	string s, t; cin >> s >> t;
	int n = int(s.size()), m = int(t.size());
	s = 'x' + s;
	t = 'x' + t;
	auto get_id = [&](int x, int y, int k) {
		return k * maxn * maxn + x * maxn + y;
	};
//	vt<vt<vt<bool>>> dp(n+2, vt<vt<bool>>(m+2, vt<bool>(2, false)));
	dp[get_id(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[get_id(i+1,j+1,0)] = dp[get_id(i+1,j+1,0)] || dp[get_id(i, j, k)] and s[i+1] == t[j+1];
				dp[get_id(i,j+1,1)] = dp[get_id(i,j+1,k)] || dp[get_id(i,j,k)] and (k==1 || s[i] != t[j+1]);
			}
		}
	}
	cout << (dp[get_id(n,m,0)] || dp[get_id(n,m,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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

input:

snuke
snukent

output:

Yes

result:

ok answer is YES

Test #2:

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

input:

snuke
ssnuke

output:

No

result:

ok answer is NO

Test #3:

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

input:

babaaaabaabbabbbbaaabaabbbbbbaaaababababbbbaabbaaaababababaaabaababbaaabbbbaabbbbbbbabaaabbaaaaabbbbabbabaabbbaaabaababbbabbaababbaaaababbaabbbaabbbababbbb
baabbaababaaabababababbabbaabbbabbbbaaaabbabaababbababbaabbbaababaabbbabbbaabaabbababaababbaaabbaaababbaaaabbababababbbaaabbababababbbaaabbbabab...

output:

Yes

result:

ok answer is YES

Test #4:

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

input:

babbbaabbababaababaabaaaabaaabbbbabaabaaabaaaabaabbabbbababaababaaabbbaaabbbbaabbbaababbbbaaababaaabaaaaaaabaabbbbaaaabbabbbaabbaaaabbbbabbbbaaaabaaabbbaaa
bbbaabaabbbababbbbabbabbababaaaabbabbaababababbabbaababbaaabaaaabbaaababaabaabaaabbbbabaabbabbaaaabaaabaaaaabbaaabaabbaabaaabbbabbbbbaaabaaaabbb...

output:

No

result:

ok answer is NO

Test #5:

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

input:

aabbbabbbaabbbaabbabaababbbabbbbabbaaababbabbaaabababaabaaabbbaaaabbaaaabbaaababaababbbbbbbaaaababaaabbaabbbaababbabbaaabaaababbbaabbbabaabbaaababbaaabaabb
abaaababbabbbabbaabaabbbaabaaaababbabbabbbbbabbaaaaaabaabbbbbbbbabbbbbabbbbbbbbabaaaabaababbbabbbbababaababbaabbaabbabaaabaabaabaabbabbaaabbabaa...

output:

Yes

result:

ok answer is YES

Test #6:

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

input:

abababbaababaaaababbaaaaabbbbbbbbbbabababbbbbbbabbaabbabaabaaaabbbaababbbbabaababbabbabbbaaabbaaababbaaaaababbbaaaabaabaaaabaabbbbbaaaaaaaabaaababaabbbaaaa
abaaababababaababbababbaabaababaaabababaaababbbaaabaaaabbaababababaaaabababababbabbabbababababbbababaabbbabaabababbabbabbababababababababbabaabb...

output:

Yes

result:

ok answer is YES

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3780kb

input:

aabbababababbbaaaaaabbaababbbbaaaaabaabaabaabbbabaaabaabaababbbabababbababababbbbabaaabaabbabaabbababbaaaabbaaaaabaabaabbbbaaabbbbaaaabababbaaaababbbbaaaba
aaaabbaabbbbbaaabbaabaabbababbabbaabaaabbbababbbbbaaaaabaaabbbaaaabbbaaababaabbabaabbaaaabbbbbbabaababbaabbbababaabbbbbababbbbaaabbbbaabaaabaaba...

output:

Yes

result:

wrong answer expected NO, found YES