Submission #1188384

#TimeUsernameProblemLanguageResultExecution timeMemory
1188384pcheloveksBrperm (RMI20_brperm)C++20
0 / 100
205 ms327680 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") //#pragma GCC target("bmi,bmi2,popcnt,lzcnt") //Andrusha Holod did not qualify to IOI 2025 ))) //Hope Andrusha Holod will win IOI 2026 #include "brperm.h" #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <cmath> #include <fstream> #include <climits> #include <queue> #include <algorithm> #include <stdint.h> #include <stack> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <cstring> // Для memset #define endl '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair < ull, ull > piu; typedef pair <ll, ll> pii; typedef pair <ld, ld> pdd; const ll DIM = 500007; const ll MXMASK = (1 << 21); const ll INF = 1e18; const ll mod = 1e9 + 123; const ld eps = 0.00000000001; const ld gr = (sqrt(5) + 1) / 2; const ll offset = 10000; const ll Bits = 20; const ll dx[5] = { -1, -1, 0, 1, 0 }; const ll dy[5] = { -1, 0, -1, 0, 1 }; FILE* stream; ll getval(char val) { return val - 'a' + 1; } class polyHash { public: const ll base = 31; vector < ll > powll; vector < ull > powull; vector < ll > prefll; vector < ull > prefull; void count(const string& s) { ll n = s.length(); powll.resize(n + 7); powull.resize(n + 7); prefll.resize(n + 7); prefull.resize(n + 7); powll[0] = 1; powull[0] = 1; for (int i = 1; i <= n; i++) { powll[i] = (powll[i - 1] * base) % mod; powull[i] = (powull[i - 1] * base); if (powll[i] < 0) powll[i] += mod; } prefll[0] = 0; prefull[0] = 0; for (int i = 1; i <= n; i++) { prefll[i] = ((prefll[i - 1] * base) + getval(s[i - 1])) % mod; prefull[i] = (prefull[i - 1] * base) + getval(s[i - 1]); if (prefll[i] < 0) prefll[i] += mod; } } piu gethash(ll L, ll R) { ll len = R - L + 1; ll hashll = prefll[R] - (powll[len] * prefll[L - 1]) % mod; ull hashull = prefull[R] - (powull[len] * prefull[L - 1]); if (hashll < 0) hashll += mod; return { hashll, hashull }; } piu mergeHash(piu h1, piu h2, ll len) { piu res; res.first = (h1.first * powll[len] + h2.first) % mod; res.second = h1.second * powull[len] + h2.second; if (res.first < 0) res.first += mod; return res; } }; polyHash h; piu H[DIM][15][15]; vector < ll > powers(30); void init(int n, const char s[]) { h.count(s); ll r = 1, p = 0; while (2 * r <= n) { r *= 2; p++; } powers[0] = 1; for (int i = 1; i <= p; i++) powers[i] = (2 * powers[i - 1]) % mod; for (int i = n - 1; i >= 0; i--) { for (int k = 0; k <= p; k++) { for (int j = 0; j <= p; j++) { //cout << i << " " << k << " " << j << endl; if (n - i < powers[j] * (powers[k] - 1) + 1) continue; if (k == 0) H[i][j][k] = h.gethash(i + 1, i + 1); else { H[i][j][k] = h.mergeHash(H[i][j + 1][k - 1], H[i + powers[j]][j + 1][k - 1], powers[k - 1]); } } } } } int query(int i, int k) { if (h.gethash(i + 1, i + powers[k]) == H[i][0][k]) return true; return false; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...