QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54860#4187. Decrypting ZodiacSa3tElSefrWA 3ms4032kbC++2.6kb2022-10-10 23:11:262022-10-10 23:11:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-10 23:11:30]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4032kb
  • [2022-10-10 23:11:26]
  • 提交

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'