QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234672 | #4187. Decrypting Zodiac | Fyind# | TL | 4ms | 5940kb | C++20 | 2.5kb | 2023-11-01 20:39:43 | 2023-11-01 20:39:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef int ll;
const int maxn = 3e5 + 5;
const ll MOD = 998244353;
const ll G = 3, Gi = 332748118;
inline ll mul(ll a, ll b) {
return (1ll*a * b) % MOD;
}
ll fpow(ll a, ll n) {
a %= MOD; ll ret = 1;
for (; n; n >>= 1, a = mul(a, a) )
if (n & 1) ret = mul(ret, a);
return ret;
}
void ntt(vector<ll> &a, int len, int op) {
while (sz(a) < len) a.push_back(0);
vector<int> R(len);
R[0] = 0;
for (int i = 1;i < len; ++i) {
R[i] = (R[i>>1]>>1) + (i&1)*(len>>1);
if (i < R[i]) swap(a[i], a[R[i]]);
}
for(int mid = 1; mid < len; mid <<= 1) {
ll Wn = fpow( op == 1 ? G : Gi , (MOD - 1) / (mid << 1));
for(int j = 0; j < len; j += (mid << 1)) {
ll w = 1;
for(int k = 0; k < mid; k++, w = mul(w, Wn)) {
ll x = a[j + k], y = mul(w, a[j + k + mid]);
a[j + k] = (x + y) % MOD,
a[j + k + mid] = (x - y + MOD) % MOD;
}
}
}
ll iv = fpow(len, MOD - 2);
if (op == -1) for(int i = 0; i < len; i++) a[i] = mul(a[i], iv);
}
vector<ll> convolution(vector<ll>& a, vector<ll>& b) {
int len = 1;
int lans = sz(a) + sz(b) - 1;
while (len < lans) len <<= 1;
ntt(a, len, 1);
ntt(b, len, 1);
vector<ll> ret(lans);
for (int i = 0;i < len; ++i) a[i] = mul(a[i], b[i]);
ntt(a, len, -1);
for (int i = 0;i < lans; ++i) ret[i] = a[i];
return ret;
}
int n, m;
int A[maxn], B[maxn], C[maxn];
int solve() {
vector<int> eq(n*2);
for (int c = 0;c < 26; ++c) {
vector<ll> polya(n), polyc(n*2);
for (int i = 0;i < n; ++i) polya[i] = A[n-i] == c;
for (int i = 0;i < n*2; ++i) polyc[i] = C[i+1] == c;
auto poly = convolution(polya, polyc);
for (int i = n-1;i < n*2; ++i) {
eq[i] += poly[i];
}
}
return n - *max_element(eq.begin()+n-1, eq.end());
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1;i <= n; ++i) {
char c; cin >> c;
A[i] = c - 'a';
}
for (int i = 1;i <= n; ++i) {
char c; cin >> c;
B[i] = c - 'a';
}
int ans = 1e9;
for (int k = 0;k <= 25; ++k) {
for (int i = 1;i <= n; ++i) {
C[i] = (B[i] + k) % 26;
C[i + n] = C[i];
}
ans = min(ans, solve());
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5940kb
input:
6 drhmex zodiac
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 3ms
memory: 5704kb
input:
8 dicepara paradise
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 4ms
memory: 3892kb
input:
13 lvlvdvdqsonwk thisisasample
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Time Limit Exceeded
input:
150000 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...