fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pii pair<int,int>
  4. #define fi first
  5. #define se second
  6. #define bit(n,i) (n>>i)&1
  7. using namespace std;
  8. const int N=1e3+5;
  9. const int S=305;
  10. string s;
  11. int n;
  12. int g[35][35];
  13. vector<pii>luu;
  14. bitset<S>L[S][35],R[S][35];
  15. main()
  16. {
  17.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  18.     freopen("transform.inp","r",stdin);
  19.     freopen("transform.out","w",stdout);
  20.     cin>>s;
  21.     int m=s.size();
  22.     s=' '+s;
  23.     cin>>n;
  24.     for(int i=1;i<=n;i++){
  25.         char x,u,v;cin>>x>>u>>v;
  26.         x-='a';u-='a';v-='a';
  27.         if(!g[u][v])luu.push_back({u,v});
  28.         g[u][v]|=(1ll<<x);
  29.     }
  30.     for(int i=1;i<=m;i++){
  31.         int x=s[i]-'a';
  32.         L[i][x].set(i);
  33.         R[i][x].set(i-1);
  34.     }
  35.     for(int len=2;len<=m;len++){
  36.         for(int i=1;i<=m-len+1;i++){
  37.             int j=i+len-1;
  38.             for(auto [u,v]:luu){
  39.                 if((L[i][u]&R[j][v]).any()){
  40.                     for(int mask=g[u][v];mask;mask-=mask&-mask){
  41.                         int x=__builtin_ctzll(mask);
  42.                         L[i][x].set(j);
  43.                         R[j][x].set(i-1);
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     int ok=0;
  50.     for(int x=0;x<26;x++)if(L[1][x][m])cout<<char(x+'a'),ok=1;
  51.     if(!ok)cout<<"No Solution.";
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yuNTig
language:
C++14 (gcc 8.3)
created:
1 day 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!