QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431265 | #4187. Decrypting Zodiac | kevinyang# | TL | 2ms | 4096kb | C++14 | 2.4kb | 2024-06-05 08:28:00 | 2024-06-05 08:28:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a)
x /= n;
}
}
template<typename T>
vector<T> multiply(vector<T> const& a, vector<T> const& b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < a.size() + b.size())
n <<= 1;
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
fft(fa, true);
vector<T> result(n);
for (int i = 0; i < n; i++)
result[i] = round(fa[i].real());
return result;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
string s,t;
cin >> s >> t;
vector<int>a(n);
vector<int>b(n);
for(int i = 0; i<n; i++){
a[i] = s[i]-'a';
b[i] = t[i]-'a';
}
vector<vector<int>>idx(26);
vector<vector<int>>idx2(26);
for(int i = 0; i<n; i++){
idx[a[i]].push_back(i);
idx2[b[i]].push_back(i);
}
int ans = 0;
for(int dx = 0; dx<26; dx++){
vector<int>dp(n);
for(int x = 0; x<26; x++){
vector<int>ar(n+1);
vector<int>br(n+1);
for(int i: idx[x]){
ar[i] = 1;
}
for(int i: idx2[(x+dx)%26]){
br[n-i] = 1;
}
vector<int>c = multiply(ar,br);
for(int i = 0; i<c.size(); i++){
dp[i%n]+=c[i];
}
}
for(int i = 0; i<n; i++){
ans = max(ans,dp[i]);
}
}
cout << n-ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4020kb
input:
6 drhmex zodiac
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
8 dicepara paradise
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
13 lvlvdvdqsonwk thisisasample
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Time Limit Exceeded
input:
150000 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...