Advertisement
Guest User

Untitled

a guest
Mar 27th, 2015
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #pragma warning (disable : 4996)
  2. #include <iostream>
  3. #include <fstream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <string>
  7. #include <set>
  8. #include <map>
  9. #include <cassert>
  10. #include <ctime>
  11. #include <iomanip>
  12.  
  13. using namespace std;
  14. #define sz size()
  15. #define all(x) x.begin(),x.end()
  16. #define forn(i,n) for (int i = 0; i<int(n); i++)
  17. #define mp make_pair
  18. typedef long long ll;
  19. typedef long double ld;
  20. const ll INF = 1e9 + 9;
  21.  
  22. bool check(string &a, string &b, vector<int> &v, vector<int> &v1){
  23.     if (a.sz != b.sz)
  24.         return false;
  25.     for (int i = 0; i < a.size(); i++){
  26.         int x = a[i] - 'a', y = b[i] - 'a';
  27.         if (v[x] != -1 && v[x] != y || v1[y]!=-1 && v1[y]!=x)
  28.             return false;
  29.         if (v[x] == -1){
  30.             v[x] = y;
  31.         }
  32.         if (v1[y] == -1){
  33.             v1[y] = x;
  34.         }
  35.     }
  36.     return true;
  37. }
  38.  
  39. void solve(){
  40.     int n;
  41.     cin >> n;
  42.     vector<string> vs(n);
  43.     for (int i = 0; i < vs.size(); i++){
  44.         cin >> vs[i];
  45.     }
  46.     string str;
  47.     cin >> str;
  48.     vector<int> v(30, -1);
  49.     vector<int> v1(30, -1);
  50.     bool good = false;
  51.     for (int i = 0; i < vs.size(); i++){
  52.         vector<int> qv(30,-1), qv1(30,-1);
  53.         if (check(vs[i], str, qv, qv1)){
  54.             good = true;
  55.             for (int j = 0; j < 30; j++){              
  56.                 if (-2 == v[j] || -1 == qv[j])
  57.                     continue;
  58.                 if (-1 == v[j]){
  59.                     if (-1 == v1[qv[j]]){
  60.                         v1[qv[j]] = j;
  61.                         v[j] = qv[j];
  62.                     }
  63.                     else if (-2 == v1[qv[j]]){
  64.                         v[j] = -2;
  65.                     }
  66.                     else if (v1[qv[j]] != j){
  67.                         v[v1[qv[j]]] = -2;
  68.                         v1[qv[j]] = -2;
  69.                         v[j] = -2;
  70.                     }
  71.                 }
  72.                 else if (v[j] != qv[j]){
  73.                     v[j] = -2;
  74.                 }
  75.             }
  76.         }
  77.     }
  78.     string code;
  79.     cin >> code;
  80.     if (!good){
  81.         cout << "IMPOSSIBLE" << endl;
  82.         return;
  83.     }
  84.     for (int i = 0; i < code.size(); i++){
  85.         int x = code[i] - 'a';
  86.         if (v[x] == -2 || v[x] == -1)
  87.             cout << "?";
  88.         else
  89.             cout << (char)(v[x] + 'a');
  90.     }
  91.     cout << endl;
  92. }
  93.  
  94. int main(){
  95.     freopen("input.txt", "r", stdin);
  96.     freopen("output.txt", "w", stdout);
  97.  
  98.     int test;
  99.     cin >> test;
  100.     for (int i = 0; i < test; i++){
  101.         solve();
  102.     }
  103.  
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement