Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma warning (disable : 4996)
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <set>
- #include <map>
- #include <cassert>
- #include <ctime>
- #include <iomanip>
- using namespace std;
- #define sz size()
- #define all(x) x.begin(),x.end()
- #define forn(i,n) for (int i = 0; i<int(n); i++)
- #define mp make_pair
- typedef long long ll;
- typedef long double ld;
- const ll INF = 1e9 + 9;
- bool check(string &a, string &b, vector<int> &v, vector<int> &v1){
- if (a.sz != b.sz)
- return false;
- for (int i = 0; i < a.size(); i++){
- int x = a[i] - 'a', y = b[i] - 'a';
- if (v[x] != -1 && v[x] != y || v1[y]!=-1 && v1[y]!=x)
- return false;
- if (v[x] == -1){
- v[x] = y;
- }
- if (v1[y] == -1){
- v1[y] = x;
- }
- }
- return true;
- }
- void solve(){
- int n;
- cin >> n;
- vector<string> vs(n);
- for (int i = 0; i < vs.size(); i++){
- cin >> vs[i];
- }
- string str;
- cin >> str;
- vector<int> v(30, -1);
- vector<int> v1(30, -1);
- bool good = false;
- for (int i = 0; i < vs.size(); i++){
- vector<int> qv(30,-1), qv1(30,-1);
- if (check(vs[i], str, qv, qv1)){
- good = true;
- for (int j = 0; j < 30; j++){
- if (-2 == v[j] || -1 == qv[j])
- continue;
- if (-1 == v[j]){
- if (-1 == v1[qv[j]]){
- v1[qv[j]] = j;
- v[j] = qv[j];
- }
- else if (-2 == v1[qv[j]]){
- v[j] = -2;
- }
- else if (v1[qv[j]] != j){
- v[v1[qv[j]]] = -2;
- v1[qv[j]] = -2;
- v[j] = -2;
- }
- }
- else if (v[j] != qv[j]){
- v[j] = -2;
- }
- }
- }
- }
- string code;
- cin >> code;
- if (!good){
- cout << "IMPOSSIBLE" << endl;
- return;
- }
- for (int i = 0; i < code.size(); i++){
- int x = code[i] - 'a';
- if (v[x] == -2 || v[x] == -1)
- cout << "?";
- else
- cout << (char)(v[x] + 'a');
- }
- cout << endl;
- }
- int main(){
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int test;
- cin >> test;
- for (int i = 0; i < test; i++){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement