fork download
copy 
  1. /* Author : Triet Do Thanh - FPT University */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl           '\n'
  6. #define int            long long
  7.  
  8. using namespace        std;
  9.  
  10. typedef pair<int, int> ii;
  11.  
  12. const int       N      = 1e6 + 7;
  13. const long long oo     = 1e18 + 7;
  14. const long long MOD    = 1e9 + 7;
  15. const int base = 311;
  16.  
  17. int n, q, k;
  18. int dp[(1 << 15)];
  19.  
  20. int h[2][N], pw[N], a[N];
  21.  
  22. int get(int op, int l, int r) {
  23.    if (op == 1) {
  24.       int _l = l;
  25.       l = n - r + 1;
  26.       r = n - _l + 1;
  27.    }
  28.    return (h[op][r] - h[op][l - 1] * pw[r - l + 1] + MOD * MOD) % MOD;
  29. }
  30.  
  31. bool check(int l, int r) {
  32.    return get(0, l, r) == get(1, l, r);
  33. }
  34.  
  35. #define bit(mask, i) (mask & (1ll << i))
  36. #define on(mask, i) (mask | (1ll << i))
  37. #define off(mask, i) (mask | ~(1ll << i))
  38.  
  39. void solve() {
  40.    string s, t;
  41.    cin >> s;
  42.    n = s.size();
  43.    t = s;
  44.    reverse(t.begin(), t.end());
  45.    s = " " + s;
  46.    t = " " + t;
  47.    pw[0] = 1;
  48.    for (int i = 1; i <= n; ++i) {
  49.       h[0][i] = (h[0][i - 1] * base + s[i] - 'a' + 1) % MOD;
  50.       h[1][i] = (h[1][i - 1] * base + t[i] - 'a' + 1) % MOD;
  51.       pw[i] = (pw[i - 1] * base) % MOD;
  52.    }
  53.    cin >> q;
  54.    while (q--) { 
  55.       int k; cin >> k;
  56.       for (int i = 1; i <= k; ++i) cin >> a[i];
  57.       for (int mask = 0; mask < (1 << k); ++mask) {
  58.          dp[mask] = oo;
  59.       }
  60.       dp[0] = 0;
  61.       for (int mask = 0; mask < (1 << k); ++mask) {
  62.          for (int i = 1; i <= k; ++i) {
  63.             if (bit(mask, i - 1)) continue;
  64.             int len = a[i];
  65.             for (int j = dp[mask] + 1; j <= n - a[i] + 1; ++j) {
  66.                if (check(j, j + len - 1)) {
  67.                   dp[on(mask, i - 1)] = min(dp[on(mask, i - 1)], j + len - 1); 
  68.                   break;
  69.                }
  70.             }
  71.          }
  72.       }
  73.       if (dp[(1 << k) - 1] != oo) cout << "YES" << endl;
  74.       else cout << "NO" << endl;
  75.    }
  76. }
  77.  
  78. #define TASK "test"
  79.  
  80. signed main()
  81. {
  82.    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  83.    if (fopen("input.txt", "r")) {
  84.       freopen("input.txt", "r", stdin);
  85.       freopen("output.txt", "w", stdout);
  86.    }
  87.    solve();
  88.    return 0;
  89. }
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d4e0K3
language:
C++14 (gcc 8.3)
created:
25 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!