QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185373 | #4187. Decrypting Zodiac | rgnerdplayer# | AC ✓ | 3640ms | 448320kb | C++20 | 2.5kb | 2023-09-21 22:11:41 | 2023-09-21 22:11:41 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'