QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234650 | #4187. Decrypting Zodiac | Fyind# | TL | 2ms | 5808kb | C++17 | 2.9kb | 2023-11-01 20:21:18 | 2023-11-01 20:21:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 3e5 + 5;
typedef double ld;
const ld PI = acos((ld)-1);
struct cp {
ld x, y;
cp(ld x=0, ld y=0) : x(x),y(y) {}
cp operator + (const cp &c) const {
return cp(x+c.x, y+c.y);
}
cp operator - (const cp &c) const {
return cp(x-c.x, y-c.y);
}
cp operator * (const cp &c) const {
return cp(x*c.x - y*c.y, x*c.y + y*c.x);
}
cp conj() const {
return cp(x, -y);
}
};
void fft(vector<cp> &a, int len, int op) {
while (sz(a) < len) a.push_back(cp(0,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]]);
}
vector<cp> w(len/2); w[0] = cp(1,0);
for (int n = 2; n <= len; n <<= 1) {
cp wt = cp(cos(2*PI*op/n), sin(2*PI*op/n));
for (int k = 1;k < n/2; ++k) {
if (k % 2) w[k] = w[k>>1] * w[k>>1] * wt;
else w[k] = w[k>>1] * w[k>>1];
}
for (int i = 0; i < len; i += n) {
int po = i + (n>>1);
for (int k = 0; k < n/2; ++k) {
auto t = a[i+k];
a[i + k] = t + w[k] * a[po + k];
a[po + k] = t - w[k] * a[po + k];
}
}
}
if (!~op)
for (int i = 0;i < len; ++i) a[i].x /= len;
}
vector<cp> convolution(vector<cp>& a, vector<cp>& b) {
int len = 1;
int lans = sz(a) + sz(b) - 1;
while (len < lans) len <<= 1;
fft(a, len, 1);
fft(b, len, 1);
vector<cp> ret(lans);
for (int i = 0;i < len; ++i) a[i] = a[i] * b[i];
fft(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<cp> polya(n), polyc(n*2);
for (int i = 0;i < n; ++i) polya[i] = {(double)(A[n-i] == c), 0};
for (int i = 0;i < n*2; ++i) polyc[i] = {(double)(C[i+1] == c), 0};
auto poly = convolution(polya, polyc);
for (int i = n-1;i < n*2; ++i) {
eq[i] += (int)(poly[i].x+0.5);
}
}
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: 2ms
memory: 5744kb
input:
6 drhmex zodiac
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5728kb
input:
8 dicepara paradise
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5808kb
input:
13 lvlvdvdqsonwk thisisasample
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Time Limit Exceeded
input:
150000 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...