Submission #1094813

#TimeUsernameProblemLanguageResultExecution timeMemory
1094813alexddBrperm (RMI20_brperm)C++17
50 / 100
3058 ms2076 KiB
#include "brperm.h" #include <bits/stdc++.h> using namespace std; int n; const long long MOD = 1e9+9; long long p[530005]; int put(int a, int exp) { if(exp==0) return 1; if(exp%2==0) return put(a*a%MOD,exp/2); else return put(a*a%MOD,exp/2)*a%MOD; } int rev(int x, int k) { int aux=0; for(int i=0;i<k;i++) if(((1<<i)&x)) aux += (1<<(k-i-1)); return aux; } long long hsh[500005][19]; long long normal[500005][19]; char S[500005]; void init(int copn, const char s[]) { n=copn; for(int i=0;i<n;i++) S[i] = s[i]; /*p[0]=1; p[1]=31; for(int i=2;i<=(1<<19);i++) p[i] = (p[i-1]*p[1])%MOD; for(int i=0;i<n;i++) { hsh[i][0] = normal[i][0] = S[i]; } for(int k=1;k<19;k++) { for(int i=0;i+(1<<k)-1<n;i++) { hsh[i][k] = (hsh[i][k-1] + hsh[i+(1<<(k-1))][k-1]*p[(1<<(18-k))])%MOD; for(int j=0;j<(1<<k);j++) { normal[i][k] = (normal[i][k] + S[i+j]*p[j*(1<<(18-k))])%MOD; } } }*/ } int query(int i, int k) { if(i+(1<<k)-1 >= n) return 0; for(int j=0;j<(1<<k);j++) if(S[i+j]!=S[i+rev(j,k)]) return 0; return 1; return hsh[i][k] == normal[i][k]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...