fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using DHASH = pair<unsigned long long, int>;
  8. const int MOD = 1e9 + 7;
  9.  
  10. DHASH operator + (const DHASH &a, const DHASH &b) {return {a.ft + b.ft, (a.sc + b.sc) % MOD};}
  11. DHASH operator - (const DHASH &a, const DHASH &b) {return {a.ft - b.ft, (a.sc - b.sc + MOD) % MOD};}
  12. DHASH operator * (const DHASH &a, const DHASH &b) {return {a.ft * b.ft, a.sc * b.sc % MOD};}
  13. DHASH DH(int x) {return {x, x % MOD};}
  14.  
  15. const int inf = 1e9 + 7;
  16. const int N = 1e4 + 5;
  17. const int T = 2e2 + 5, K = 13 + 5;
  18. const DHASH BASE = DH(31);
  19. const int MSK = (1 << 13);
  20.  
  21. string s;
  22. DHASH S[N], R[N], POW[N];
  23. int n, t;
  24. int k[T], l[T][K];
  25. int dp[MSK + 100];
  26.  
  27.  
  28. DHASH getDHASH(int l, int r) {return S[r] - S[l - 1] * POW[r - l + 1];}
  29. DHASH getDHASHR(int l, int r) {return R[l] - R[r + 1] * POW[r - l + 1];}
  30. bool isPalin(int l, int r) {return getDHASH(l, r) == getDHASHR(l, r);}
  31.  
  32. vector<int> a;
  33. int ID[N];
  34. void compress() {
  35.     for (int i = 1; i <= t; i++) {
  36.         for (int j = 1; j <= k[i]; j++) a.push_back(l[i][j]);
  37.     }
  38.     sort(a.begin(), a.end());
  39.     a.resize(distance(a.begin(), unique(a.begin(), a.end())));
  40.     for (int i = 0; i < a.size(); i++) ID[a[i]] = i;
  41. }
  42. const int MAXSZ = T * K;
  43. int nxt[MAXSZ][N];
  44.  
  45. void init() {
  46.     for (int len: a) {
  47.         int cur = inf;
  48.         for (int i = n; i >= 1; i--) {
  49.             if (i + len - 1<= n && isPalin(i, i + len - 1)) cur = i;
  50.             nxt[ID[len]][i] = cur;
  51.         }
  52.     }
  53. }
  54. signed main() {
  55.     cin.tie(NULL)->sync_with_stdio(false);
  56.     if(ifstream("Input.inp")) {
  57.         freopen("Input.inp", "r", stdin);
  58.         freopen("Output.out", "w", stdout);
  59.     }
  60.     cin >> s >> t;
  61.     for (int i =1; i <= t; i++) {
  62.         cin >> k[i];
  63.         for (int j = 1; j <= k[i]; j++) cin >> l[i][j];
  64.     }
  65.  
  66.     n = s.size(); s = ' ' + s;
  67.     POW[0] = DH(1);
  68.     for (int i = 1; i <= n; i++) POW[i] = POW[i - 1] * BASE;
  69.     for (int i = 1; i <= n; i++) S[i] = S[i - 1] * BASE + DH(s[i] - 'a' + 1);
  70.     for (int i = n; i >= 1; i--) R[i] = R[i + 1] * BASE + DH(s[i] - 'a' + 1);
  71.  
  72.     compress();
  73.     init();
  74.  
  75.     for (int o = 1; o <= t; o++) {
  76.         int sz = k[o]; 
  77.         int fullmsk = (1 << sz) - 1;
  78.         fill(dp, dp + (1 << sz), inf);
  79.         dp[0] = 0;
  80.         for (int msk = 0; msk <= fullmsk; msk++) if (dp[msk] <= n) {
  81.             int curEnd = dp[msk];
  82.             if (curEnd == n) continue;
  83.             for (int i = 1; i <= sz; i++) if (!(msk >> (i - 1) & 1)) {
  84.                 int len = l[o][i];
  85.                 int start = nxt[ID[len]][curEnd + 1];
  86.                 if (start <= n) {
  87.                     int nmsk = msk | (1 << (i - 1));
  88.                     dp[nmsk] = min(dp[nmsk], start + len - 1);
  89.                 }
  90.             }
  91.         }
  92.         cout << (dp[fullmsk] <= n ? "YES" : "NO") << "\n";
  93.     }
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 5676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LItx4D
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!