Submission #398732

#TimeUsernameProblemLanguageResultExecution timeMemory
398732MilosMilutinovicBrperm (RMI20_brperm)C++14
100 / 100
1700 ms34428 KiB
/** * author: milos * created: 04.05.2021 20:27:22 **/ #include <bits/stdc++.h> #include "brperm.h" using namespace std; const int N = 500050; string s = ""; vector<pair<int, int>> a(N); vector<vector<int>> cnt(N, vector<int>(2)); void Calc(int n) { for (int i = 0; i < n; i++) { int j = i, cnt = 0, res = 0; while (j) { res = res * 2 + j % 2; cnt++; j /= 2; } a[i] = {res, cnt}; } } void init(int n, const char seq[]) { for (int i = 0; i < n; i++) { s += seq[i]; if (i > 0) { cnt[i][0] = cnt[i - 1][0]; cnt[i][1] = cnt[i - 1][1]; } if (s[i] == 'a') { cnt[i][0] += 1; } if (s[i] == 'b') { cnt[i][1] += 1; } } Calc(n); } int Rev(int x, int k) { return a[x].first * (1 << (k - a[x].second)); } int query(int i, int k) { if (i + (1 << k) > (int) s.size()) { return 0; } int L = i, R = i + (1 << k) - 1; if (cnt[R][0] - (L == 0 ? 0 : cnt[L - 1][0]) == R - L + 1) { return 1; } if (cnt[R][1] - (L == 0 ? 0 : cnt[L - 1][1]) == R - L + 1) { return 1; } for (int j = i; j < i + (1 << k); j++) { if (s[j] != s[i + Rev(j - i, k)]) { 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...