제출 #479416

#제출 시각아이디문제언어결과실행 시간메모리
479416tranxuanbachPalindromic Partitions (CEOI17_palindromic)C++17
100 / 100
223 ms15956 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (int i = l; i < r; i++) #define ForE(i, l, r) for (int i = l; i <= r; i++) #define FordE(i, l, r) for (int i = l; i >= r; i--) #define Fora(v, a) for (auto v: a) #define bend(a) a.begin(), a.end() #define isz(a) ((signed)a.size()) using ll = long long; using ld = long double; using pii = pair <int, int>; using vi = vector <int>; using vpii = vector <pii>; using vvi = vector <vi>; #define hash __hash__ mt19937 rando(chrono::steady_clock::now().time_since_epoch().count()); int randt(int l, int r){ return rando() % (r - l + 1) + l; } const int N = 1e6 + 5, base = 31; int mod; inline void sadd(int& x, int y){ if ((x += y) >= mod) x -= mod; return; } inline int add(int x, int y){ if ((x += y) >= mod) x -= mod; return x; } inline void ssub(int& x, int y){ if ((x -= y) < 0) x += mod; return; } inline int sub(int x, int y){ if ((x -= y) < 0) x += mod; return x; } inline int mul(int x, int y){ return 1ll * x * y % mod; } inline int binpow(int x, int y){ int ans = 1; while (y){ if (y & 1) ans = mul(ans, x); x = mul(x, x); y >>= 1; } return ans; } inline int inv(int x){ return binpow(x, mod - 2); } #define div __div__ inline int div(int x, int y){ return mul(x, binpow(y, mod - 2)); } int fac[N], invfac[N]; void calfac(){ fac[0] = invfac[0] = 1; For(i, 1, N){ fac[i] = mul(fac[i - 1], i); } invfac[N - 1] = binpow(fac[N - 1], mod - 2); FordE(i, N - 2, 1){ invfac[i] = mul(invfac[i + 1], i + 1); } } inline int C(int n, int k){ if (n < 0 or k < 0 or k > n){ return 0; } return mul(fac[n], mul(invfac[k], invfac[n - k])); } inline int P(int n, int k){ if (n < 0 or k < 0 or k > n){ return 0; } return mul(fac[n], invfac[n - k]); } bool isprime(int x){ if (x <= 1){ return 0; } if (x <= 3){ return 1; } if (x % 2 == 0 or x % 3 == 0){ return 0; } for (int i = 5; i * i <= x; i += 6){ if (x % i == 0 or x % (i + 2) == 0){ return 0; } } return 1; } int n; string s; int pwbase[N]; int hash[N]; int calhash(int l, int r){ return sub(hash[r], mul(hash[l - 1], pwbase[r - l + 1])); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("KEK.inp", "r", stdin); // freopen("KEK.out", "w", stdout); { mod = randt(500000000, 1000000000); while (!isprime(mod)){ mod++; } } pwbase[0] = 1; For(i, 1, N){ pwbase[i] = mul(pwbase[i - 1], base); } int tests; cin >> tests; while (tests--){ cin >> s; n = isz(s); s = ' ' + s; ForE(i, 1, n){ hash[i] = add(mul(hash[i - 1], base), s[i] - 'a' + 1); } int l = 1, r = n, ll = 1, rr = n, ans = 0; while (ll < rr){ if (calhash(l, ll) == calhash(rr, r)){ ans += 2; l = ll + 1; r = rr - 1; } ll++; rr--; } if (l <= r){ ans++; } cout << ans << endl; } } /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...