#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 = 2205 + 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;
string s, t;
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<n; ++i){
ret += at(b, i);
}
// cout << s << ' ' << t << " : " << ret << endl;
return ret;
}
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));
int ans = 0;
for(int i=0; i<b.size(); ++i){
ans = max(ans, solve_tc(a, b));
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:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i=0; i<t.size(); ++i) {
| ~^~~~~~~~~
rowords.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int idx=0; idx<s.size(); ++idx) {
| ~~~^~~~~~~~~
rowords.cpp: In function 'int main()':
rowords.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0; i<b.size(); ++i){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
6 ms |
204 KB |
Output is correct |
| 7 |
Correct |
116 ms |
320 KB |
Output is correct |
| 8 |
Incorrect |
120 ms |
204 KB |
Output isn't correct |
| 9 |
Correct |
110 ms |
320 KB |
Output is correct |
| 10 |
Correct |
110 ms |
300 KB |
Output is correct |
| 11 |
Correct |
122 ms |
312 KB |
Output is correct |
| 12 |
Correct |
145 ms |
284 KB |
Output is correct |
| 13 |
Correct |
162 ms |
304 KB |
Output is correct |
| 14 |
Correct |
130 ms |
308 KB |
Output is correct |
| 15 |
Correct |
164 ms |
204 KB |
Output is correct |
| 16 |
Correct |
116 ms |
332 KB |
Output is correct |
| 17 |
Incorrect |
69 ms |
324 KB |
Output isn't correct |
| 18 |
Correct |
133 ms |
204 KB |
Output is correct |
| 19 |
Correct |
111 ms |
204 KB |
Output is correct |
| 20 |
Incorrect |
118 ms |
204 KB |
Output isn't correct |
| 21 |
Correct |
16 ms |
204 KB |
Output is correct |
| 22 |
Correct |
29 ms |
204 KB |
Output is correct |
| 23 |
Correct |
45 ms |
204 KB |
Output is correct |
| 24 |
Incorrect |
46 ms |
304 KB |
Output isn't correct |
| 25 |
Incorrect |
66 ms |
204 KB |
Output isn't correct |
