QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54858 | #4187. Decrypting Zodiac | abdelrahman001 | AC ✓ | 7402ms | 507840kb | C++ | 2.7kb | 2022-10-10 23:00:49 | 2022-10-10 23:00:51 |
Judging History
answer
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
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<cd> mul(vector<cd> a, vector<cd> &b) {
int n = a.size();
for (int i = 0; i < n; i++)
a[i] *= b[i];
return a;
}
vector<cd> add(vector<cd> a, vector<cd> b) {
int n = a.size();
for(int i = 0;i < n;i++)
a[i] += b[i];
return a;
}
int n;
string s, t;
vector<int> a[26], b[26];
vector<cd> 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++)
ret[i] = (s[i] == c);
return ret;
}
int solve(int shift) {
vector<cd> res;
for(int i = 0, j = shift;i < 26;i++, j = (j + 1) % 26) {
if(i == 0)
res = mul(fa[i], fb[j]);
else
res = add(res, mul(fa[i], fb[j]));
}
fft(res, 1);
vector<int> ret;
for(int i = 0;i < res.size();i++)
ret.push_back(round(res[i].real()));
int mx = 0;
for(int i = 0;i < ret.size();i++)
mx = max(mx, ret[i]);
return mx;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s >> t;
s += s;
reverse(t.begin(), t.end());
for(int i = 0;i < 26;i++) {
a[i] = get(s, i + 'a');
b[i] = get(t, i + 'a');
}
int x = 1;
while(x < a[0].size() + b[0].size())
x <<= 1;
for(int i = 0;i < 26;i++) {
fa[i] = vector<cd>(a[i].begin(), a[i].end());
fb[i] = vector<cd>(b[i].begin(), b[i].end());
fa[i].resize(x);
fb[i].resize(x);
fft(fa[i], 0);
fft(fb[i], 0);
}
int mx = 0;
for(int i = 0;i < 26;i++)
mx = max(mx, solve(i));
cout << n - mx << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 4012kb
input:
6 drhmex zodiac
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
8 dicepara paradise
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4012kb
input:
13 lvlvdvdqsonwk thisisasample
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 7273ms
memory: 507840kb
input:
150000 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
output:
144230
result:
ok single line: '144230'
Test #5:
score: 0
Accepted
time: 7208ms
memory: 507752kb
input:
150000 cccccccccccccmtccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccmfcrcccccccucccccccccccucccccccccyccoccccccccccccacccccbccccccccccccccccccccnccccccccccccccccccccclcccccccccccccccccccccckcccccccccccccccpcccccccccccccccccccccccbcccccqcccccccqccccccnycccceksckccccccccocccccccccccccc...
output:
144104
result:
ok single line: '144104'
Test #6:
score: 0
Accepted
time: 7298ms
memory: 507712kb
input:
150000 cccccccccccccctccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccckcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
output:
144188
result:
ok single line: '144188'
Test #7:
score: 0
Accepted
time: 7402ms
memory: 507756kb
input:
150000 mlskccoxctpexrrfygtjtckjutzjaictbppyuovjxmgqdsxliigkbtdwuujwvbxcmmrahkynldbzdrhoanxhutnowdtrxjnenxplkrvzmvepxxnqoocplxcsidexplfcxzceufqfmghnkheurcllsnemhezbfqwmybtwqzjcxbbkarxeksjpnybqsomqfvpthtmrxvvhudntwobvhaklxmrqztpgfookwjdiypuljrpaduxbcoetirlejsbrknpojgtpusveqhegiuldicojiouondcjuehkbimsr...
output:
144230
result:
ok single line: '144230'
Test #8:
score: 0
Accepted
time: 7335ms
memory: 507752kb
input:
150000 kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...
output:
144090
result:
ok single line: '144090'
Test #9:
score: 0
Accepted
time: 7314ms
memory: 507696kb
input:
150000 kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...
output:
144187
result:
ok single line: '144187'
Test #10:
score: 0
Accepted
time: 7164ms
memory: 507800kb
input:
150000 nznanssdgutbwweyrmqhsotgvpcmajgeadjfexuzplxsivkozqowgigmoqdcwxmghhxyvszawdfclouotbxgfbzlpkaqoaibnynprylvcmsiuednvvktkejdxumuzgbgjlbtihkngtfeylpaqjvpefwthivnyzcvdhbgpachfwedzoftelhqhxuoekikmwuvvsfddirosgexgavdvgmroyrymssksjlefclhukwydtlkxtocgmkaajstnrisujibvzryeveimcqjniivemqnsmrdpwgvecmyazttd...
output:
143804
result:
ok single line: '143804'
Test #11:
score: 0
Accepted
time: 7200ms
memory: 507768kb
input:
150000 bhftmhqtqmltcxnygxqkozrwaqxuxczsiwrlcvsrbhzepxeggxlypsrabjessnegslpshvoaisjhranqqbhbeyebgfyozkchylzblleblohrjtfwrzbolmrkznqvkjnvclxdbeekzcbkewywjcdaubuuclsmxcslyzjiqagvrhqcktoadebtvyutdcawpfryybymlhcyxvbueumjaaclysshpttutcdfltsbzrbdcskomliuboedgdhnknrewztlbscoxnvzpdshqiaawnmenhkbbjmdgpupoqhgo...
output:
143849
result:
ok single line: '143849'
Test #12:
score: 0
Accepted
time: 7197ms
memory: 507664kb
input:
150000 fpagchsakklabymmpmyrsluqaqlupcshghcsnxkczhzhfzoztumdxgfubgpejktldbosntfuvraojcrvhwaasesmytilkwxecqewxzpitjowvrbdbdcahyigvonvqzasixpazorauoohlekwedequqhtuixyepiqnjotjhxdryyhwafsfcpidwzzplbfjdlutbmxlojjfaoeuqxgtitwcpzinbxacumzezlpjotuzvaymdjocnsfkzohmgosbnbhrbcxkzogplntxwweoshuuroeonqhhxbkpdqkh...
output:
143837
result:
ok single line: '143837'
Test #13:
score: 0
Accepted
time: 7217ms
memory: 507692kb
input:
150000 gjodcowfpbskvjhwilokpquumtimojricrslxqibrlesfbvlzyzidfscqtunhcmcbilztxsktwkcwfashgqbfesfbjwbtkykbfjyfbcxtvbftmyideiigieuhwhfoywkexdjlttpdskgarwujsasnbpgbegewrzqenohsxxicuxexnvxitfejocqscxyaqaczzarplydezbolwnunueyeygbfltdatzusyieotlexeqmlqexqmkrzxkbuiexstdemftnjqykqmdmxnozakbuvwhrjlnhgyjhixodd...
output:
143811
result:
ok single line: '143811'
Test #14:
score: 0
Accepted
time: 7238ms
memory: 507748kb
input:
150000 koyqowexlfpmfayhxjgnjysiwjlmhxtvymxwuglrckdwjwbnrnhsfqhgsrodzmzrvpgboqaimsssofirxfzrcnqcwbjmzcrqredlkfdbfwqtmkjqkamtjkdtlhhvsdldpapeqyyaueosatvoptdsxxojxenjlfivtjpofziaxajrarlptfwxekujrlqzvblimmzvndhctolswmygpcdkizuggfeuqblufxptosakasoseecrfspxxmxhlvfscslhruafsgpirpikhfhoxbclgnbuxeqpfhekqupov...
output:
143871
result:
ok single line: '143871'
Test #15:
score: 0
Accepted
time: 2ms
memory: 4040kb
input:
6 dabccd dddcaa
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 2ms
memory: 4000kb
input:
5 aaabb aabbb
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
9 aaaaabbbb aaaabbbba
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 2ms
memory: 4056kb
input:
26 abcdefghijklmnopqrstuvwxyz zabcdefghijklmnopqrstuvwxy
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 4ms
memory: 4128kb
input:
27 abcdefghijklmnopqrstuvwxyzz zabcdefghijklmnopqrstuvwxyy
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 2ms
memory: 4088kb
input:
27 abcdefghijklmnopqrstuvwxyzz zabcdefghijklmnopqrstuvwxyz
output:
0
result:
ok single line: '0'
Test #21:
score: 0
Accepted
time: 3ms
memory: 4016kb
input:
6 dabcbc dccbdb
output:
4
result:
ok single line: '4'
Test #22:
score: 0
Accepted
time: 3ms
memory: 3940kb
input:
4 ahfa ddgc
output:
2
result:
ok single line: '2'
Test #23:
score: 0
Accepted
time: 19ms
memory: 5932kb
input:
630 wkwyxtwpzwrjyvejrfpkucfycvypdlbvmkdjmqtekyyjgpqbipesqsgwjylhzzmqnempgwnqdrulvwdzgqvazopkwokqatoympmqwryctalziacdrkuaouwpnyrogvslrvkwtyldxatuvavtwzghlcjdrmvkocbnlzmpctcjqzcgieeevankgwpltjizarhvusncppcnizrgknhqigjgvafkdlfbnifzgwsnpiuaroejqbtortuitqzkwdusgeetqdxoxdiojqcejqrocmlyirbggfotvujllgfjlhgs...
output:
572
result:
ok single line: '572'
Test #24:
score: 0
Accepted
time: 18ms
memory: 5708kb
input:
511 ifiiieiihihihiigfghhhifiigghhiiiihifiihhiiiiihehihiieiieiighhigigighihhiiedhihidgiiiiiighgigiiiighghgiicihhhhiiihiihfggihiiihhheigighhifihiighihhfiiihgiigiiiihifhiiigiihhgiigiificiihibifgghhhihgihhifiihfhidghiiihihihhhihiiiihihihfhiihiieiigihhhghahhiiigiihgiihhihfdhheigihhifhhghfiiiihifiihiiiiii...
output:
342
result:
ok single line: '342'
Test #25:
score: 0
Accepted
time: 23ms
memory: 5896kb
input:
630 lhgyfhveuevynekxrpdznfjptsajghiqzsonmxktelvxbmfzwkdxsuzaoavxivezsryqnbfhslsrsroplapvvoazujudfatzoijkelxdprhkktlfzwoohzqszjmmrfyofcqahavmluplqoocffxesjmduxgnmdevhhuksfkoompcaagujirfscajkbenarpidfzoproxbgkmvnvsqlixxtmhxtujoixjjonfiojriyrdqbeewcblvnahqxlolacawirgwzpryrbwpecwhxtwbsxnxzpedylwnzsthjsz...
output:
588
result:
ok single line: '588'
Test #26:
score: 0
Accepted
time: 19ms
memory: 5784kb
input:
511 hiighiigiiihfgiifighiiiigfiihfiihiiggihiiihihiiiighihghiiihciieihihgiiifiihgihihihiifihhiiiiihigiihiihhhgeiigfiigiihiiiiighihiehhifihihcihggiihhehhghididhiiiciifiihhieiihiiihhchhhhihhihhhbighiiiiighhiiihhdiggihiiieiiihgihigiegehiihiifhhiigigiiifiihiihiihfieghhiggigiighhhifidiigieiihiiifafgiiihig...
output:
364
result:
ok single line: '364'
Test #27:
score: 0
Accepted
time: 28ms
memory: 5656kb
input:
511 hhiiiiigiidiiihidihiihhehhigdihgiighiifiigiiifihiigfiighigiiiiihiiiheegihiiiggiiiiiiihghhiicigggigihihfhihgghgfiiigfhihihiifgiehfiihghehfhhhigihhhihfiggifihhiiihhgihihgighgihhhihhighiiiihfiigiifhhigiihigiihahieehhiihhifiihiifhfhhihhhiihhiiifhiihiiiiihhgigfihiheigfigiihiihifhihiiiiiihhhihhhiiihgi...
output:
476
result:
ok single line: '476'
Test #28:
score: 0
Accepted
time: 3ms
memory: 3900kb
input:
4 aabb abba
output:
0
result:
ok single line: '0'