QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185373#4187. Decrypting Zodiacrgnerdplayer#AC ✓3640ms448320kbC++202.5kb2023-09-21 22:11:412023-09-21 22:11:41

Judging History

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

  • [2023-09-21 22:11:41]
  • 评测
  • 测评结果:AC
  • 用时:3640ms
  • 内存:448320kb
  • [2023-09-21 22:11:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr double PI = numbers::pi;

void dft(vector<complex<double>> &a) {
    int n = a.size();
    if (n == 1) { return; }
    vector<int> rev(n);
    int k = __builtin_ctz(n) - 1;
    for (int i = 0; i < n; i++) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        if (rev[i] < i) {
            swap(a[rev[i]], a[i]);
        }
    }
    vector<complex<double>> roots(n);
    for (int i = 0; i < n; i++) {
        roots[i] = exp(2 * PI / n * i * complex<double>(0, 1));
    }
    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) {
            for (int j = 0; j < k; j++) {
                auto u = a[i + j], v = a[i + j + k] * roots[n / (2 * k) * j];
                a[i + j] = u + v;
                a[i + j + k] = u - v;
            }
        }
    }
}

void idft(vector<complex<double>> &a) {
    int n = a.size();
    reverse(a.begin() + 1, a.end());
    dft(a);
    for (int i = 0; i < n; i++) {
        a[i] /= n;
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    auto solve = [&]() {
        int n;
        cin >> n;

        string s, t;
        cin >> s >> t;
        s += s;
        reverse(t.begin(), t.end());

        int sz = 1;
        while (sz < 3 * n - 1) {
            sz *= 2;
        }

        constexpr int A = 26;

        vector a(A, vector<complex<double>>(sz)), b(a);
        for (int c = 0; c < A; c++) {
            for (int i = 0; i < 2 * n; i++) {
                if (s[i] - 'a' == c) {
                    a[c][i] = 1;
                }
            }
            for (int i = 0; i < n; i++) {
                if (t[i] - 'a' == c) {
                    b[c][i] = 1;
                }
            }
            dft(a[c]);
            dft(b[c]);
        }

        int ans = n + 1;

        for (int c = 0; c < A; c++) {
            vector<complex<double>> res(sz);
            for (int i = 0; i < A; i++) {
                int j = (i + c) % A;
                for (int x = 0; x < sz; x++) {
                    res[x] += a[i][x] * b[j][x];
                }
            }
            idft(res);
            int match = 0;
            for (int i = 0; i < n; i++) {
                int x = round(res[i + n - 1].real());
                match = max(match, x);
            }
            ans = min(ans, n - match);
        }
        
        cout << ans << '\n';
    };

    solve();

    return 0;
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3660kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 3441ms
memory: 448204kb

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144230

result:

ok single line: '144230'

Test #5:

score: 0
Accepted
time: 3465ms
memory: 448316kb

input:

150000
cccccccccccccmtccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccmfcrcccccccucccccccccccucccccccccyccoccccccccccccacccccbccccccccccccccccccccnccccccccccccccccccccclcccccccccccccccccccccckcccccccccccccccpcccccccccccccccccccccccbcccccqcccccccqccccccnycccceksckccccccccocccccccccccccc...

output:

144104

result:

ok single line: '144104'

Test #6:

score: 0
Accepted
time: 3579ms
memory: 448092kb

input:

150000
cccccccccccccctccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccckcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144188

result:

ok single line: '144188'

Test #7:

score: 0
Accepted
time: 3640ms
memory: 448184kb

input:

150000
mlskccoxctpexrrfygtjtckjutzjaictbppyuovjxmgqdsxliigkbtdwuujwvbxcmmrahkynldbzdrhoanxhutnowdtrxjnenxplkrvzmvepxxnqoocplxcsidexplfcxzceufqfmghnkheurcllsnemhezbfqwmybtwqzjcxbbkarxeksjpnybqsomqfvpthtmrxvvhudntwobvhaklxmrqztpgfookwjdiypuljrpaduxbcoetirlejsbrknpojgtpusveqhegiuldicojiouondcjuehkbimsr...

output:

144230

result:

ok single line: '144230'

Test #8:

score: 0
Accepted
time: 3510ms
memory: 448184kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144090

result:

ok single line: '144090'

Test #9:

score: 0
Accepted
time: 3543ms
memory: 448320kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144187

result:

ok single line: '144187'

Test #10:

score: 0
Accepted
time: 3326ms
memory: 448052kb

input:

150000
nznanssdgutbwweyrmqhsotgvpcmajgeadjfexuzplxsivkozqowgigmoqdcwxmghhxyvszawdfclouotbxgfbzlpkaqoaibnynprylvcmsiuednvvktkejdxumuzgbgjlbtihkngtfeylpaqjvpefwthivnyzcvdhbgpachfwedzoftelhqhxuoekikmwuvvsfddirosgexgavdvgmroyrymssksjlefclhukwydtlkxtocgmkaajstnrisujibvzryeveimcqjniivemqnsmrdpwgvecmyazttd...

output:

143804

result:

ok single line: '143804'

Test #11:

score: 0
Accepted
time: 3577ms
memory: 448116kb

input:

150000
bhftmhqtqmltcxnygxqkozrwaqxuxczsiwrlcvsrbhzepxeggxlypsrabjessnegslpshvoaisjhranqqbhbeyebgfyozkchylzblleblohrjtfwrzbolmrkznqvkjnvclxdbeekzcbkewywjcdaubuuclsmxcslyzjiqagvrhqcktoadebtvyutdcawpfryybymlhcyxvbueumjaaclysshpttutcdfltsbzrbdcskomliuboedgdhnknrewztlbscoxnvzpdshqiaawnmenhkbbjmdgpupoqhgo...

output:

143849

result:

ok single line: '143849'

Test #12:

score: 0
Accepted
time: 3623ms
memory: 448248kb

input:

150000
fpagchsakklabymmpmyrsluqaqlupcshghcsnxkczhzhfzoztumdxgfubgpejktldbosntfuvraojcrvhwaasesmytilkwxecqewxzpitjowvrbdbdcahyigvonvqzasixpazorauoohlekwedequqhtuixyepiqnjotjhxdryyhwafsfcpidwzzplbfjdlutbmxlojjfaoeuqxgtitwcpzinbxacumzezlpjotuzvaymdjocnsfkzohmgosbnbhrbcxkzogplntxwweoshuuroeonqhhxbkpdqkh...

output:

143837

result:

ok single line: '143837'

Test #13:

score: 0
Accepted
time: 3517ms
memory: 448048kb

input:

150000
gjodcowfpbskvjhwilokpquumtimojricrslxqibrlesfbvlzyzidfscqtunhcmcbilztxsktwkcwfashgqbfesfbjwbtkykbfjyfbcxtvbftmyideiigieuhwhfoywkexdjlttpdskgarwujsasnbpgbegewrzqenohsxxicuxexnvxitfejocqscxyaqaczzarplydezbolwnunueyeygbfltdatzusyieotlexeqmlqexqmkrzxkbuiexstdemftnjqykqmdmxnozakbuvwhrjlnhgyjhixodd...

output:

143811

result:

ok single line: '143811'

Test #14:

score: 0
Accepted
time: 3508ms
memory: 448156kb

input:

150000
koyqowexlfpmfayhxjgnjysiwjlmhxtvymxwuglrckdwjwbnrnhsfqhgsrodzmzrvpgboqaimsssofirxfzrcnqcwbjmzcrqredlkfdbfwqtmkjqkamtjkdtlhhvsdldpapeqyyaueosatvoptdsxxojxenjlfivtjpofziaxajrarlptfwxekujrlqzvblimmzvndhctolswmygpcdkizuggfeuqblufxptosakasoseecrfspxxmxhlvfscslhruafsgpirpikhfhoxbclgnbuxeqpfhekqupov...

output:

143871

result:

ok single line: '143871'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

6
dabccd
dddcaa

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

5
aaabb
aabbb

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

9
aaaaabbbb
aaaabbbba

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

26
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxy

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyy

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyz

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

6
dabcbc
dccbdb

output:

4

result:

ok single line: '4'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

4
ahfa
ddgc

output:

2

result:

ok single line: '2'

Test #23:

score: 0
Accepted
time: 7ms
memory: 4876kb

input:

630
wkwyxtwpzwrjyvejrfpkucfycvypdlbvmkdjmqtekyyjgpqbipesqsgwjylhzzmqnempgwnqdrulvwdzgqvazopkwokqatoympmqwryctalziacdrkuaouwpnyrogvslrvkwtyldxatuvavtwzghlcjdrmvkocbnlzmpctcjqzcgieeevankgwpltjizarhvusncppcnizrgknhqigjgvafkdlfbnifzgwsnpiuaroejqbtortuitqzkwdusgeetqdxoxdiojqcejqrocmlyirbggfotvujllgfjlhgs...

output:

572

result:

ok single line: '572'

Test #24:

score: 0
Accepted
time: 3ms
memory: 4804kb

input:

511
ifiiieiihihihiigfghhhifiigghhiiiihifiihhiiiiihehihiieiieiighhigigighihhiiedhihidgiiiiiighgigiiiighghgiicihhhhiiihiihfggihiiihhheigighhifihiighihhfiiihgiigiiiihifhiiigiihhgiigiificiihibifgghhhihgihhifiihfhidghiiihihihhhihiiiihihihfhiihiieiigihhhghahhiiigiihgiihhihfdhheigihhifhhghfiiiihifiihiiiiii...

output:

342

result:

ok single line: '342'

Test #25:

score: 0
Accepted
time: 7ms
memory: 4932kb

input:

630
lhgyfhveuevynekxrpdznfjptsajghiqzsonmxktelvxbmfzwkdxsuzaoavxivezsryqnbfhslsrsroplapvvoazujudfatzoijkelxdprhkktlfzwoohzqszjmmrfyofcqahavmluplqoocffxesjmduxgnmdevhhuksfkoompcaagujirfscajkbenarpidfzoproxbgkmvnvsqlixxtmhxtujoixjjonfiojriyrdqbeewcblvnahqxlolacawirgwzpryrbwpecwhxtwbsxnxzpedylwnzsthjsz...

output:

588

result:

ok single line: '588'

Test #26:

score: 0
Accepted
time: 3ms
memory: 4728kb

input:

511
hiighiigiiihfgiifighiiiigfiihfiihiiggihiiihihiiiighihghiiihciieihihgiiifiihgihihihiifihhiiiiihigiihiihhhgeiigfiigiihiiiiighihiehhifihihcihggiihhehhghididhiiiciifiihhieiihiiihhchhhhihhihhhbighiiiiighhiiihhdiggihiiieiiihgihigiegehiihiifhhiigigiiifiihiihiihfieghhiggigiighhhifidiigieiihiiifafgiiihig...

output:

364

result:

ok single line: '364'

Test #27:

score: 0
Accepted
time: 3ms
memory: 4992kb

input:

511
hhiiiiigiidiiihidihiihhehhigdihgiighiifiigiiifihiigfiighigiiiiihiiiheegihiiiggiiiiiiihghhiicigggigihihfhihgghgfiiigfhihihiifgiehfiihghehfhhhigihhhihfiggifihhiiihhgihihgighgihhhihhighiiiihfiigiifhhigiihigiihahieehhiihhifiihiifhfhhihhhiihhiiifhiihiiiiihhgigfihiheigfigiihiihifhihiiiiiihhhihhhiiihgi...

output:

476

result:

ok single line: '476'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

4
aabb
abba

output:

0

result:

ok single line: '0'