QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54848 | #4187. Decrypting Zodiac | T3alaadl3k2olyehymn3k | TL | 3ms | 4044kb | C++ | 2.6kb | 2022-10-10 21:14:46 | 2022-10-10 21:14:49 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using cd = complex<double>;
const double PI = acos(-1);
int reverse(int num, int lg_n) {
int res = 0;
for (int i = 0; i < lg_n; i++) {
if (num & (1 << i))
res |= 1 << (lg_n - 1 - i);
}
return res;
}
void fft(vector<cd> &a, bool invert) {
int n = a.size();
int lg_n = 0;
while ((1 << lg_n) < n)
lg_n++;
for (int i = 0; i < n; i++) {
if (i < reverse(i, lg_n))
swap(a[i], a[reverse(i, lg_n)]);
}
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;
}
}
vector<int> multiply(vector<int> const &a, vector<int> 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<int> result(n);
for (int i = 0; i < n; i++)
result[i] = round(fa[i].real());
return result;
}
const int N = 1e6;
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n;
cin >> n;
string s, zod;
cin >> s >> zod;
string alt1 = s, alt2 = zod + zod;
s.clear(), zod.clear();
for (char i: alt1)s += i, s += (' ');
for (char i: alt2)zod += i, zod += i;
vector<int> poly1(s.size() * 26), poly2(zod.size() * 26);
int p1 = 0, p2 = 0;
for (auto i: s) {
for (int j = 0; j < 26; j++) {
if (i - 'a' == j)poly1[p1++] = 1;
else
poly1[p1++] = 0;
}
}
for (auto i: zod)
for (int j = 0; j < 26; j++) {
if (i - 'a' == j)poly2[p2++] = 1;
else
poly2[p2++] = 0;
}
reverse(poly1.begin(), poly1.end());
auto res = multiply(poly1, poly2);
int ans = 0, cur = 0;
for (int i = poly1.size() - 1; i < poly2.size(); i++) {
if (cur % (2 * 26) < 26)ans = max(ans, res[i]);
cur++;
}
cout << n - ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4024kb
input:
6 drhmex zodiac
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
8 dicepara paradise
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 3ms
memory: 4000kb
input:
13 lvlvdvdqsonwk thisisasample
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Time Limit Exceeded
input:
150000 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...