QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54848#4187. Decrypting ZodiacT3alaadl3k2olyehymn3kTL 3ms4044kbC++2.6kb2022-10-10 21:14:462022-10-10 21:14:49

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 21:14:49]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:4044kb
  • [2022-10-10 21:14:46]
  • 提交

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...

output:


result: