QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54842 | #4187. Decrypting Zodiac | Sa3tElSefr | AC ✓ | 5860ms | 509036kb | C++ | 2.8kb | 2022-10-10 20:27:49 | 2022-10-10 20:27:50 |
Judging History
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;
}
詳細信息
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'