#include<bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define uint unsigned long long
#define ull unsigned __int128
const int LEN = 64;
const int MAX = 3010 + LEN;
inline bool at(uint a[], int i){
return a[i/LEN] & ((uint)1 << (i%LEN));
}
inline bool tog(uint a[], int i) {
return a[i/LEN] ^= ((uint)1 << (i%LEN));
}
int n;
uint a[MAX/LEN], b[MAX/LEN], cs[26][MAX/LEN];
void solve(uint c[]){
//sliding b -> a
memcpy(a, b, sizeof(b));
memset(b, 0, sizeof(b));
// b = (a << 1) | 1
uint carry = 1;
for(int i=0; i<n/LEN; ++i) {
b[i] = (a[i] << 1) | carry;
carry = bool(a[i] & ((uint)1<<(LEN-1)));
}
// b = -b = ~b + 1
for(int i=0; i<n/LEN; ++i) b[i] = ~b[i];
for(int i=0; i<n; ++i) if(tog(b, i)) break;
// a |= c, b += a, b &= a, b ^= a
carry = 0;
for(int i=0; i<n/LEN; ++i) {
a[i] |= c[i];
ull tmp = b[i]; tmp += a[i]; tmp += carry;
b[i] = tmp & (~(uint)0);
carry = tmp >> LEN;
b[i] &= a[i];
b[i] ^= a[i];
}
}
int solve_tc(string s, string t) {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(cs, 0, sizeof(cs));
// init c['A'] ~ c['Z']
for(int i=0; i<t.size(); ++i) {
tog(cs[t[i] - 'a'], i);
}
n = (t.size()/LEN+1)*LEN;
for(int idx=0; idx<s.size(); ++idx) {
char c = s[idx];
solve(cs[c - 'a']);
}
int ret = 0;
for(int i=0; i<t.size(); ++i){
ret += at(b, i);
}
// cout << s << ' ' << t << " : " << ret << endl;
return ret;
}
int dp[MAX][MAX];
void chk_naive(string s, string t, int ret) {
memset(dp, 0, sizeof(dp));
for(int i=1; i<=s.size(); ++i) {
for(int j=1; j<=t.size(); ++j) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if(s[i-1] == t[j-1])
dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
}
}
if(dp[s.size()][t.size()] != ret) {
cout << s << endl << t;
exit(1);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
string a, b;
cin >> a >> b;
for(char c : a) assert(islower(c));
for(char c : b) assert(islower(c));
// srand(4546);
// for(int i=0; i<2000; ++i) a.push_back('a' + (rand()%26));
// for(int i=0; i<2000; ++i) b.push_back('a' + (rand()%26));
int ans = 0;
for(int i=0; i<b.size(); ++i){
int ret = solve_tc(a, b);
chk_naive(a, b, ret);
ans = max(ans, ret);
b.push_back(b[0]);
b.erase(b.begin());
}
cout << ans;
}
Compilation message
rowords.cpp: In function 'int solve_tc(std::string, std::string)':
rowords.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i=0; i<t.size(); ++i) {
| ~^~~~~~~~~
rowords.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int idx=0; idx<s.size(); ++idx) {
| ~~~^~~~~~~~~
rowords.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0; i<t.size(); ++i){
| ~^~~~~~~~~
rowords.cpp: In function 'void chk_naive(std::string, std::string, int)':
rowords.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=1; i<=s.size(); ++i) {
| ~^~~~~~~~~~
rowords.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int j=1; j<=t.size(); ++j) {
| ~^~~~~~~~~~
rowords.cpp: In function 'int main()':
rowords.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i=0; i<b.size(); ++i){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
37196 KB |
Output isn't correct |
| 2 |
Correct |
60 ms |
37292 KB |
Output is correct |
| 3 |
Correct |
96 ms |
37316 KB |
Output is correct |
| 4 |
Correct |
246 ms |
37280 KB |
Output is correct |
| 5 |
Correct |
162 ms |
37280 KB |
Output is correct |
| 6 |
Correct |
461 ms |
37292 KB |
Output is correct |
| 7 |
Execution timed out |
2085 ms |
37296 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2098 ms |
37244 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2099 ms |
37196 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2098 ms |
37208 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2083 ms |
37196 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2085 ms |
37200 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2078 ms |
37204 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2094 ms |
37256 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2090 ms |
37196 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2091 ms |
37196 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2080 ms |
37196 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2090 ms |
37236 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2097 ms |
37196 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2091 ms |
37196 KB |
Time limit exceeded |
| 21 |
Correct |
810 ms |
37196 KB |
Output is correct |
| 22 |
Correct |
1531 ms |
37196 KB |
Output is correct |
| 23 |
Execution timed out |
2085 ms |
37296 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2071 ms |
37400 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2087 ms |
37196 KB |
Time limit exceeded |
