Submission #886644

#TimeUsernameProblemLanguageResultExecution timeMemory
886644CDuongBrperm (RMI20_brperm)C++17
0 / 100
1837 ms39420 KiB
#include<bits/stdc++.h> using namespace std; const int base = 29; const int mod = 1069177027; const int mxN = 5e5 + 5; int n, a[mxN]; vector<int> rev[20]; int a_hash[mxN], rev_hash[20][mxN], pw[mxN]; int get_hash(int l, int r) { return (l == 0 ? a_hash[r] : (a_hash[r] - (1ll * a_hash[l - 1] * pw[r - l + 1] % mod) + mod)) % mod; } int reverse_msk(int len, int msk) { int res = 0; for (int i = 0; i < len; ++i) { res = res << 1 | (msk & 1); msk >>= 1; } return res; } void init(int N, const char S[]) { n = N; for (int i = 0; i < N; ++i) { a[i] = S[i] - 'a'; a_hash[i] = (1ll * (i ? a_hash[i - 1] : 0) * base + a[i]) % mod; pw[i] = (i ? 1ll * pw[i - 1] * base % mod : 1ll); } for (int len = 1; len <= 3; ++len) { rev[len].resize(1 << len); for (int msk = 0; msk < 1 << (len - len / 2); ++msk) { rev[len][msk] = reverse_msk(len, msk); // cout << rev[len][msk] << " "; } // cout << endl; for (int st = 0; st + (1 << (len - len / 2)) <= N; ++st) { int cur_hash = 0; for (int i = 0; i < 1 << (len - len / 2); ++i) cur_hash = (1ll * cur_hash * base + a[st + rev[len][i]]) % mod; rev_hash[len][st] = cur_hash; // cout << len << " " << st << " " << rev_hash[len][st] << endl; } } } int query(int st, int k) { for (int i = 0; i < 1 << (k / 2); ++i) { int ahead = (1 << (k - k / 2)) * i; int nst = st + ahead; cout << "nst = " << nst << " " << st + reverse_msk(k, ahead) << endl; cout << get_hash(nst, nst + (1 << (k - k / 2)) - 1) << endl; cout << rev_hash[k][st + reverse_msk(k, ahead)] << endl; if (get_hash(nst, nst + (1 << (k - k / 2)) - 1) != rev_hash[k][st + reverse_msk(k, ahead)]) return 0; } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...