QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#440563 | #7262. String Modification | I_Love_Sonechka# | WA | 1ms | 4036kb | C++17 | 1.3kb | 2024-06-13 20:42:37 | 2024-06-13 20:42:41 |
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());
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;
}
Details
Tip: Click on the bar to expand more detailed information
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