fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define dou double
  5. #define pii pair<int,int>
  6. #define pll pair<ll,ll>
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define FOR(i,a,b) for(int i=(a); i<=(b); i++)
  11. #define FORD(i,a,b) for(int i=(a); i>=(b); i--)
  12. #define REP(i,a,b) for(int i=(a); i<(b); i++)
  13. #define el '\n'
  14. #define all(x) (x).begin(), (x).end()
  15. const int maxN = 2e5;
  16. const int maxM = 3e3;
  17. const int LOG = 20;
  18. const int mod = (int)1e9 + 7;
  19. const ll oo = 1e18;
  20.  
  21. int query;
  22.  
  23. namespace subtask1
  24. {
  25.     int n, a[maxN+5];
  26.     string s;
  27.  
  28.     string cal(string x)
  29.     {
  30.         string temp = " ";
  31.         FOR(i,1,n)
  32.         {
  33.             int idx = a[i];
  34.             temp += x[idx];
  35.         }
  36.         return temp;
  37.     }
  38.  
  39.     void solve()
  40.     {
  41.         cin >> n;
  42.         cin >> s;
  43.         s = " " + s;
  44.         FOR(i,1,n) cin >> a[i];
  45.         set<string> st;
  46.         queue<pair<string, int>> q;
  47.         q.push({s, 0});
  48.         while(!q.empty())
  49.         {
  50.             string x = q.front().fi;
  51.             int kc = q.front().se;
  52.             q.pop();
  53.             string newX = cal(x);
  54.  
  55.             if(newX == s) 
  56.             {
  57.                 cout << kc + 1 << el;
  58.                 break;
  59.             }
  60.             else if(!st.count(newX)) q.push({newX, kc+1});
  61.         }
  62.     }
  63. }
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. int main()
  71. {
  72.     ios_base::sync_with_stdio(0); cin.tie(0);
  73.     #define task "safe"
  74.     if(fopen(task".inp", "r"))
  75.     {
  76.         freopen(task".inp", "r", stdin);
  77.         freopen(task".out", "w", stdout);
  78.     }
  79.     cin >> query;
  80.     while(query--)subtask1::solve();
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YlhGmZ
language:
C++ (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!