QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54842#4187. Decrypting ZodiacSa3tElSefrAC ✓5860ms509036kbC++2.8kb2022-10-10 20:27:492022-10-10 20:27:50

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 20:27:50]
  • 评测
  • 测评结果:AC
  • 用时:5860ms
  • 内存:509036kb
  • [2022-10-10 20:27:49]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ld  double
using namespace std;

const int N = 2e5 + 5, mod = 998244353;

using cd = complex<ld>;
const ld PI = acos(-1);

void fft(vector<complex<ld>> &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){
        ld ang = 2 * PI / len;
        if(invert) ang *= -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(auto &i: a) i /= n;
    }

}
vector<complex<ld> > addition(vector<complex<ld> > fa, vector<complex<ld> > fb){
    for(int i = 0; i < fa.size(); i++) fa[i] += fb[i];
    return fa;
}
vector<complex<ld> > multiply(vector<complex<ld> > fa, vector<complex<ld> > fb){
    for(int i = 0; i < fa.size(); i++) fa[i] *= fb[i];
    return  fa;
}

vector<vector<int> > a(26), b(26);
vector<vector<complex<ld> > > fa(26), fb(26);

vector<int> get(string &s, char c) {
    int n = s.size();
    vector<int> ret(n, 0);
    for(int i = 0; i < n; i++) {
        if(s[i] == c) {
            ret[i] = 1;
        }
    }
    return ret;
}

int n;

int solve(int shift) {

    vector<complex<ld>> res;
    for(int i = 0, j = shift; i < 26; i++, j++) {
        if(j == 26) j = 0;
        if(i == 0) {
            res = multiply(fa[i], fb[j]);
        }   else {
            res = addition(res, multiply(fa[i], fb[j]));
        }
    }

    fft(res, 1);
    vector<int> vals;
    for(auto x : res)vals.push_back((int) round(x.real()));
    int ans = n;
    for(int i = n - 1; i < n - 1 + n; i++) {
        ans = min(ans, n - vals[i]);
    }
    return ans;

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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


    for(char c = 'a'; c <= 'z'; c++) {
        a[c - 'a'] = get(s, c);
        b[c - 'a'] = get(t, c);
    }

    int ans = n;
    int n = 1;
    while (n < a[0].size() + b[0].size()) n <<= 1;

    for(int i = 0; i < 26; i++) {
        fa[i] = vector<complex<ld>>(a[i].begin(),a[i].end());
        fb[i] = vector<complex<ld>>(b[i].begin(),b[i].end());
        fa[i].resize(n);
        fb[i].resize(n);
        fft(fa[i], 0);
        fft(fb[i], 0);
    }

    for(int i = 0; i < 26; i++) {
        ans = min(ans, solve(i));
    }

    cout << ans;




    return 0;
}





Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 4016kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

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

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 2ms
memory: 4040kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 5744ms
memory: 508956kb

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144230

result:

ok single line: '144230'

Test #5:

score: 0
Accepted
time: 5779ms
memory: 508992kb

input:

150000
cccccccccccccmtccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccmfcrcccccccucccccccccccucccccccccyccoccccccccccccacccccbccccccccccccccccccccnccccccccccccccccccccclcccccccccccccccccccccckcccccccccccccccpcccccccccccccccccccccccbcccccqcccccccqccccccnycccceksckccccccccocccccccccccccc...

output:

144104

result:

ok single line: '144104'

Test #6:

score: 0
Accepted
time: 5846ms
memory: 508860kb

input:

150000
cccccccccccccctccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccckcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144188

result:

ok single line: '144188'

Test #7:

score: 0
Accepted
time: 5860ms
memory: 508980kb

input:

150000
mlskccoxctpexrrfygtjtckjutzjaictbppyuovjxmgqdsxliigkbtdwuujwvbxcmmrahkynldbzdrhoanxhutnowdtrxjnenxplkrvzmvepxxnqoocplxcsidexplfcxzceufqfmghnkheurcllsnemhezbfqwmybtwqzjcxbbkarxeksjpnybqsomqfvpthtmrxvvhudntwobvhaklxmrqztpgfookwjdiypuljrpaduxbcoetirlejsbrknpojgtpusveqhegiuldicojiouondcjuehkbimsr...

output:

144230

result:

ok single line: '144230'

Test #8:

score: 0
Accepted
time: 5785ms
memory: 508888kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144090

result:

ok single line: '144090'

Test #9:

score: 0
Accepted
time: 5826ms
memory: 508896kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144187

result:

ok single line: '144187'

Test #10:

score: 0
Accepted
time: 5784ms
memory: 508808kb

input:

150000
nznanssdgutbwweyrmqhsotgvpcmajgeadjfexuzplxsivkozqowgigmoqdcwxmghhxyvszawdfclouotbxgfbzlpkaqoaibnynprylvcmsiuednvvktkejdxumuzgbgjlbtihkngtfeylpaqjvpefwthivnyzcvdhbgpachfwedzoftelhqhxuoekikmwuvvsfddirosgexgavdvgmroyrymssksjlefclhukwydtlkxtocgmkaajstnrisujibvzryeveimcqjniivemqnsmrdpwgvecmyazttd...

output:

143804

result:

ok single line: '143804'

Test #11:

score: 0
Accepted
time: 5835ms
memory: 508804kb

input:

150000
bhftmhqtqmltcxnygxqkozrwaqxuxczsiwrlcvsrbhzepxeggxlypsrabjessnegslpshvoaisjhranqqbhbeyebgfyozkchylzblleblohrjtfwrzbolmrkznqvkjnvclxdbeekzcbkewywjcdaubuuclsmxcslyzjiqagvrhqcktoadebtvyutdcawpfryybymlhcyxvbueumjaaclysshpttutcdfltsbzrbdcskomliuboedgdhnknrewztlbscoxnvzpdshqiaawnmenhkbbjmdgpupoqhgo...

output:

143849

result:

ok single line: '143849'

Test #12:

score: 0
Accepted
time: 5705ms
memory: 509036kb

input:

150000
fpagchsakklabymmpmyrsluqaqlupcshghcsnxkczhzhfzoztumdxgfubgpejktldbosntfuvraojcrvhwaasesmytilkwxecqewxzpitjowvrbdbdcahyigvonvqzasixpazorauoohlekwedequqhtuixyepiqnjotjhxdryyhwafsfcpidwzzplbfjdlutbmxlojjfaoeuqxgtitwcpzinbxacumzezlpjotuzvaymdjocnsfkzohmgosbnbhrbcxkzogplntxwweoshuuroeonqhhxbkpdqkh...

output:

143837

result:

ok single line: '143837'

Test #13:

score: 0
Accepted
time: 5760ms
memory: 508808kb

input:

150000
gjodcowfpbskvjhwilokpquumtimojricrslxqibrlesfbvlzyzidfscqtunhcmcbilztxsktwkcwfashgqbfesfbjwbtkykbfjyfbcxtvbftmyideiigieuhwhfoywkexdjlttpdskgarwujsasnbpgbegewrzqenohsxxicuxexnvxitfejocqscxyaqaczzarplydezbolwnunueyeygbfltdatzusyieotlexeqmlqexqmkrzxkbuiexstdemftnjqykqmdmxnozakbuvwhrjlnhgyjhixodd...

output:

143811

result:

ok single line: '143811'

Test #14:

score: 0
Accepted
time: 5698ms
memory: 508892kb

input:

150000
koyqowexlfpmfayhxjgnjysiwjlmhxtvymxwuglrckdwjwbnrnhsfqhgsrodzmzrvpgboqaimsssofirxfzrcnqcwbjmzcrqredlkfdbfwqtmkjqkamtjkdtlhhvsdldpapeqyyaueosatvoptdsxxojxenjlfivtjpofziaxajrarlptfwxekujrlqzvblimmzvndhctolswmygpcdkizuggfeuqblufxptosakasoseecrfspxxmxhlvfscslhruafsgpirpikhfhoxbclgnbuxeqpfhekqupov...

output:

143871

result:

ok single line: '143871'

Test #15:

score: 0
Accepted
time: 2ms
memory: 4052kb

input:

6
dabccd
dddcaa

output:

4

result:

ok single line: '4'

Test #16:

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

input:

5
aaabb
aabbb

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3992kb

input:

9
aaaaabbbb
aaaabbbba

output:

0

result:

ok single line: '0'

Test #18:

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

input:

26
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxy

output:

0

result:

ok single line: '0'

Test #19:

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

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyy

output:

0

result:

ok single line: '0'

Test #20:

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

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyz

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

6
dabcbc
dccbdb

output:

4

result:

ok single line: '4'

Test #22:

score: 0
Accepted
time: 2ms
memory: 3984kb

input:

4
ahfa
ddgc

output:

2

result:

ok single line: '2'

Test #23:

score: 0
Accepted
time: 6ms
memory: 5872kb

input:

630
wkwyxtwpzwrjyvejrfpkucfycvypdlbvmkdjmqtekyyjgpqbipesqsgwjylhzzmqnempgwnqdrulvwdzgqvazopkwokqatoympmqwryctalziacdrkuaouwpnyrogvslrvkwtyldxatuvavtwzghlcjdrmvkocbnlzmpctcjqzcgieeevankgwpltjizarhvusncppcnizrgknhqigjgvafkdlfbnifzgwsnpiuaroejqbtortuitqzkwdusgeetqdxoxdiojqcejqrocmlyirbggfotvujllgfjlhgs...

output:

572

result:

ok single line: '572'

Test #24:

score: 0
Accepted
time: 12ms
memory: 5676kb

input:

511
ifiiieiihihihiigfghhhifiigghhiiiihifiihhiiiiihehihiieiieiighhigigighihhiiedhihidgiiiiiighgigiiiighghgiicihhhhiiihiihfggihiiihhheigighhifihiighihhfiiihgiigiiiihifhiiigiihhgiigiificiihibifgghhhihgihhifiihfhidghiiihihihhhihiiiihihihfhiihiieiigihhhghahhiiigiihgiihhihfdhheigihhifhhghfiiiihifiihiiiiii...

output:

342

result:

ok single line: '342'

Test #25:

score: 0
Accepted
time: 12ms
memory: 5804kb

input:

630
lhgyfhveuevynekxrpdznfjptsajghiqzsonmxktelvxbmfzwkdxsuzaoavxivezsryqnbfhslsrsroplapvvoazujudfatzoijkelxdprhkktlfzwoohzqszjmmrfyofcqahavmluplqoocffxesjmduxgnmdevhhuksfkoompcaagujirfscajkbenarpidfzoproxbgkmvnvsqlixxtmhxtujoixjjonfiojriyrdqbeewcblvnahqxlolacawirgwzpryrbwpecwhxtwbsxnxzpedylwnzsthjsz...

output:

588

result:

ok single line: '588'

Test #26:

score: 0
Accepted
time: 13ms
memory: 5792kb

input:

511
hiighiigiiihfgiifighiiiigfiihfiihiiggihiiihihiiiighihghiiihciieihihgiiifiihgihihihiifihhiiiiihigiihiihhhgeiigfiigiihiiiiighihiehhifihihcihggiihhehhghididhiiiciifiihhieiihiiihhchhhhihhihhhbighiiiiighhiiihhdiggihiiieiiihgihigiegehiihiifhhiigigiiifiihiihiihfieghhiggigiighhhifidiigieiihiiifafgiiihig...

output:

364

result:

ok single line: '364'

Test #27:

score: 0
Accepted
time: 12ms
memory: 5780kb

input:

511
hhiiiiigiidiiihidihiihhehhigdihgiighiifiigiiifihiigfiighigiiiiihiiiheegihiiiggiiiiiiihghhiicigggigihihfhihgghgfiiigfhihihiifgiehfiihghehfhhhigihhhihfiggifihhiiihhgihihgighgihhhihhighiiiihfiigiifhhigiihigiihahieehhiihhifiihiifhfhhihhhiihhiiifhiihiiiiihhgigfihiheigfigiihiihifhihiiiiiihhhihhhiiihgi...

output:

476

result:

ok single line: '476'

Test #28:

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

input:

4
aabb
abba

output:

0

result:

ok single line: '0'