QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54860 | #4187. Decrypting Zodiac | Sa3tElSefr | WA | 3ms | 4032kb | C++ | 2.6kb | 2022-10-10 23:11:26 | 2022-10-10 23:11:30 |
Judging History
answer
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<complex<double>>& a) {
int n = a.size(), L = 31 - __builtin_clz(n);
static vector<complex<long double>> R(2, 1);
static vector<complex<double>> rt(2, 1); // (^ 10% fas te r i f double)
for (static int k = 2; k < n; k *= 2) {
R.resize(n);
rt.resize(n);
auto x = polar(1.0L, acos(-1.0L) / k);
for(int i = k; i < 2 * k; i++) rt[i] = R[i] = i & 1 ? R[i / 2] * x : R[i / 2];
}
vector<int> rev(n);
for(int i = 0; i < n; i++) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
for(int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) for(int j = 0; j < k; j++) {
complex<double> z = rt[j + k] * a[i + j + k]; //
a[i + j + k] = a[i + j] - z;
a[i + j] += z;
}
}
vector<cd> mul(vector<cd> a, vector<cd> &b) {
int n = a.size();
for (int i = 0; i < n; i++)
a[i] *= b[i];
return a;
}
vector<cd> add(vector<cd> a, vector<cd> b) {
int n = a.size();
for(int i = 0;i < n;i++)
a[i] += b[i];
return a;
}
int n;
string s, t;
vector<int> a[26], b[26];
vector<cd> fa[26], fb[26];
vector<int> get(string s, char c) {
int n = s.size();
vector<int> ret(n, 0);
for(int i = 0;i < n;i++)
ret[i] = (s[i] == c);
return ret;
}
int solve(int shift) {
vector<cd> res;
for(int i = 0, j = shift;i < 26;i++, j = (j + 1) % 26) {
if(i == 0)
res = mul(fa[i], fb[j]);
else
res = add(res, mul(fa[i], fb[j]));
}
fft(res);
vector<int> ret;
for(int i = 0;i < res.size();i++)
ret.push_back(round(res[i].real()));
int mx = 0;
for(int i = 0;i < ret.size();i++)
mx = max(mx, ret[i]);
return mx;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s >> t;
s += s;
reverse(t.begin(), t.end());
for(int i = 0;i < 26;i++) {
a[i] = get(s, i + 'a');
b[i] = get(t, i + 'a');
}
int x = 1;
while(x < a[0].size() + b[0].size())
x <<= 1;
for(int i = 0;i < 26;i++) {
fa[i] = vector<cd>(a[i].begin(), a[i].end());
fb[i] = vector<cd>(b[i].begin(), b[i].end());
fa[i].resize(x);
fb[i].resize(x);
fft(fa[i]);
fft(fb[i]);
}
int mx = 0;
for(int i = 0;i < 26;i++)
mx = max(mx, solve(i));
cout << n - mx << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 4032kb
input:
6 drhmex zodiac
output:
-122
result:
wrong answer 1st lines differ - expected: '2', found: '-122'