QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #554782 | #8560. Just Shuffle the Input | PhantomThreshold# | RE | 128ms | 26392kb | C++20 | 4.4kb | 2024-09-09 15:45:02 | 2024-09-09 15:45:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace NTT{
const int MOD=998244353,g=3,ig=332748118;
const int MAXN=877777;
inline long long poww(long long x,long long y){
long long ret=1;
while (y){
if (y&1) ret=ret*x,ret%=MOD;
x*=x,x%=MOD;
y>>=1;
}
return ret;
}
inline long long inv(long long x){return poww(x,MOD-2);}
int R[MAXN];
inline void fft(vector<long long> &a,int L,int ty){
for (int i=0;i<L;i++) i>R[i]?swap(a[i],a[R[i]]):void(0);
for (int i=1;i<L;i<<=1){
long long w=poww(ty,(MOD-1)/(i<<1));
for (int j=0;j<L;j+=(i<<1)){
long long wn=1;
for (int k=j;k<i+j;k++){
long long t=wn*a[i+k]%MOD;
a[i+k]=a[k]-t;a[i+k]<0?a[i+k]+=MOD:0;
a[k]+=t;a[k]>=MOD?a[k]-=MOD:0;
wn=wn*w%MOD;
}
}
}
}
inline vector<long long> mul(vector<long long> A,vector<long long> B){
int L=1,n=(int)A.size()-1,m=(int)B.size()-1;
while (L<=n+m) L<<=1;
A.resize(L);
B.resize(L);
for (int i=1;i<L;i<<=1)
for (int j=0;j<i;j++)
R[i+j]=R[j]+L/(i<<1);
fft(A,L,g);
fft(B,L,g);
vector<long long> ret(L);
for (int i=0;i<L;i++)
ret[i]=A[i]*B[i]%MOD;
fft(ret,L,ig);
long long invL=inv(L);
for (int i=0;i<L;i++) ret[i]=ret[i]*invL%MOD;
ret.resize(n+m+1);
return ret;
}
}
namespace NTT2{
const int MOD=1004535809,g=3;
const int MAXN=877777;
inline long long poww(long long x,long long y){
long long ret=1;
while (y){
if (y&1) ret=ret*x,ret%=MOD;
x*=x,x%=MOD;
y>>=1;
}
return ret;
}
inline long long inv(long long x){return poww(x,MOD-2);}
const int ig=inv(g);
int R[MAXN];
inline void fft(vector<long long> &a,int L,int ty){
for (int i=0;i<L;i++) i>R[i]?swap(a[i],a[R[i]]):void(0);
for (int i=1;i<L;i<<=1){
long long w=poww(ty,(MOD-1)/(i<<1));
for (int j=0;j<L;j+=(i<<1)){
long long wn=1;
for (int k=j;k<i+j;k++){
long long t=wn*a[i+k]%MOD;
a[i+k]=a[k]-t;a[i+k]<0?a[i+k]+=MOD:0;
a[k]+=t;a[k]>=MOD?a[k]-=MOD:0;
wn=wn*w%MOD;
}
}
}
}
inline vector<long long> mul(vector<long long> A,vector<long long> B){
int L=1,n=(int)A.size()-1,m=(int)B.size()-1;
while (L<=n+m) L<<=1;
A.resize(L);
B.resize(L);
for (int i=1;i<L;i<<=1)
for (int j=0;j<i;j++)
R[i+j]=R[j]+L/(i<<1);
fft(A,L,g);
fft(B,L,g);
vector<long long> ret(L);
for (int i=0;i<L;i++)
ret[i]=A[i]*B[i]%MOD;
fft(ret,L,ig);
long long invL=inv(L);
for (int i=0;i<L;i++) ret[i]=ret[i]*invL%MOD;
ret.resize(n+m+1);
return ret;
}
}
typedef long long ll;
inline long long poww(long long x,long long y,long long mod){
long long ret=1;
while (y){
if (y&1) ret=ret*x,ret%=mod;
x*=x,x%=mod;
y>>=1;
}
return ret;
}
inline long long inv(long long x,long long mod){return poww(x,mod-2,mod);}
const int maxn=200000;
const ll mod=998244353;
const ll mod2=1004535809;
const ll base=114;
const ll base2=514;
ll pw[maxn+50];
ll pw2[maxn+50];
void prepare(){
pw[0]=1;
for (int i=1;i<=maxn;i++) pw[i]=pw[i-1]*base%mod;
pw2[0]=1;
for (int i=1;i<=maxn;i++) pw2[i]=pw2[i-1]*base2%mod2;
}
ll n,m;
ll p[maxn+50];
string s,t;
ll ht[maxn+50];
ll ht2[maxn+50];
int main(){
ios_base::sync_with_stdio(false);
prepare();
cin >> n >> m;
for (int i=0;i<m;i++){
cin >> p[i];
p[i]--;
}
cin >> s;
for (int i=0;i<n;i++){
ht[i]=(s[i]-'a'+1)*pw[i]%mod;
if (i>0) ht[i]=(ht[i]+ht[i-1])%mod;
ht2[i]=(s[i]-'a'+1)*pw2[i]%mod2;
if (i>0) ht2[i]=(ht2[i]+ht2[i-1])%mod2;
}
map<pair<ll,ll>,ll> dict;
for (int i=0;i+m-1<n;i++){
pair<ll,ll> ttt;
{
ll ed=ht[i+m-1];
ll st=0;
if (i>0) st=ht[i-1];
ll tmp=(ed-st+mod)*inv(pw[i],mod)%mod;
ttt.first=tmp;
}
{
ll ed=ht2[i+m-1];
ll st=0;
if (i>0) st=ht2[i-1];
ll tmp=(ed-st+mod2)*inv(pw2[i],mod2)%mod2;
ttt.second=tmp;
}
dict[ttt]++;
}
vector<int> order;
{
ll x=0;
order.emplace_back(x);
for (x=p[x];x!=0;x=p[x]){
order.emplace_back(x);
}
}
cin >> t;
vector<ll> A(m);
vector<ll> B(m+m);
vector<ll> B2(m+m);
for (int i=0;i<m;i++){
A[i]=t[order[i]]-'a'+1;
B[m-1-i+m]=B[m-1-i]=pw[order[i]];
B2[m-1-i+m]=B2[m-1-i]=pw2[order[i]];
}
vector<ll> C=NTT::mul(A,B);
vector<ll> C2=NTT2::mul(A,B2);
int pos=-1;
for (int i=0;i<m;i++) if (dict.count(make_pair(C[m+m-1-i],C2[m+m-1-i]))){pos=i;break;}
cout << pos << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12032kb
input:
3 2 2 1 aba ba
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 3ms
memory: 11964kb
input:
7 4 3 4 2 1 dcabadc abcd
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 3ms
memory: 12032kb
input:
100 10 5 3 8 10 7 1 4 9 6 2 dkrwvaottzwtarzokdvtwtarzokdvtzadtkwrvotottkwvzadrazkodtvrtwkdvtrztowakdvtrztowaazkodtvrtwzadtkwrvot dkrwvaottz
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9780kb
input:
1000 100 91 41 1 35 54 30 93 66 49 79 42 33 9 47 6 51 71 32 5 39 4 70 34 55 36 8 90 50 81 16 89 19 67 87 72 2 26 18 57 64 83 7 40 100 75 27 92 96 28 10 60 98 59 61 88 74 58 48 65 56 25 95 97 22 21 23 15 84 17 68 43 52 29 77 73 86 46 38 76 45 62 24 99 13 12 44 80 31 37 20 14 53 82 63 3 78 69 94 11 85...
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11848kb
input:
1000 10 7 3 8 5 6 1 9 4 10 2 xfxjdlbgsrxlxsrfgbjdsgjlxbrdfxsgjlxbrdfxgxbrfxjsdlxfxjdlbgsrxfxjdlbgsrdsrxgjlfxbsgjlxbrdfxxfxjdlbgsrxfxjdlbgsrdsrxgjlfxbrjdxbsflxgrjdxbsflxgxfxjdlbgsrdsrxgjlfxbfdlbsrxxgjsgjlxbrdfxgxbrfxjsdlxlxsrfgbjdjbsfxgdrlxsgjlxbrdfxrjdxbsflxgrjdxbsflxgsgjlxbrdfxxlxsrfgbjdgxbrfxjsdlb...
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 54ms
memory: 18536kb
input:
100000 100 79 16 57 73 85 76 41 34 60 54 20 19 50 67 99 80 14 9 17 40 52 65 49 12 87 8 93 70 74 94 68 100 56 36 43 28 31 58 81 96 69 83 55 23 25 90 22 2 92 26 1 30 98 35 37 62 61 95 47 5 89 84 77 38 24 48 45 3 11 97 66 44 51 42 46 72 33 13 88 91 86 32 63 39 75 10 71 27 21 64 29 7 53 4 59 82 6 78 18 ...
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 45ms
memory: 19076kb
input:
100000 1000 583 913 457 431 934 337 447 735 412 555 211 46 254 341 368 835 72 171 651 180 986 47 354 500 887 379 528 867 541 833 525 296 300 57 992 821 646 996 468 49 856 573 929 656 979 416 94 610 349 88 655 13 387 748 312 15 316 826 230 212 146 317 438 617 781 561 465 298 328 417 941 20 943 942 86...
output:
3
result:
ok 1 number(s): "3"
Test #8:
score: 0
Accepted
time: 128ms
memory: 26392kb
input:
200000 20000 6760 18178 12483 17065 11456 14033 17871 7962 5800 17761 14375 9410 18027 16141 7619 1346 15586 9306 1188 14463 8823 7941 6635 1573 111 9338 4795 587 8124 3742 13297 6999 19280 18055 13069 14941 10755 6525 17386 15651 1766 6566 13355 17546 15938 7074 17517 5655 5526 254 5433 2549 4763 7...
output:
662
result:
ok 1 number(s): "662"
Test #9:
score: 0
Accepted
time: 52ms
memory: 13456kb
input:
200000 10 9 8 7 6 10 2 4 1 5 3 gfatgztmiggizmtgfgatmzgtitafggggtfamzigtimtzgftggamzgtitafggztigmagtfgggtfamzigtimtzgftggagizmtgfgatftgagtgzmitaggfgitzmggtfamzigttaggfgitzmgizmtgfgatggtfamzigtztigmagtfgmzgtitafggagfgtimgtzggtfamzigtmzgtitafggztigmagtfgimtzgftggaagfgtimgtzgfatgztmigtaggfgitzmimtzgftgg...
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 49ms
memory: 12900kb
input:
200000 1 1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: -100
Runtime Error
input:
200000 200000 10346 154885 184424 149680 35636 48097 98625 160831 56852 149801 86780 179411 104814 6787 84033 26166 28348 147641 105020 21606 162086 51344 55220 66864 57151 15213 20770 104682 138735 30216 88163 154578 95744 77774 89460 75134 68771 5466 96323 24521 1271 86484 199015 157678 39152 1171...