fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <set>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9. 	int t;
  10. 	cin >> t;
  11. 	for(int T = 0; T < t; T++) {
  12. 		int n, m;
  13. 		cin >> n;
  14. 		vector<string> users(n);	
  15. 		for(int i = 0; i < n; i++) 
  16. 			cin >> users[i];
  17. 		cin >> m;
  18. 		string curr;
  19. 		vector<string> messages(m);
  20. 		vector<vector<int>> memo(m, vector<int> (n, -1));
  21. 		for(int i = 0; i < m; i++) {
  22. 			getline(cin, curr);
  23. 			if(curr.empty())
  24. 				getline(cin, curr);
  25. 			string speaker;
  26. 			set<string> other;
  27. 			int j = 0;
  28. 			while(curr[j] != ':') speaker += curr[j++];
  29. 			messages[i] = curr.substr(speaker.size());
  30. 			string temp;
  31. 			while(++j < curr.size()) {
  32. 				if(curr[j] == '.' or curr[j] == ',' or curr[j] == '!' 
  33. 					or curr[j] == '?' or curr[j] == ' ') {
  34. 					other.insert(temp);
  35. 					temp.clear();
  36. 				}
  37. 				else
  38. 					temp += curr[j];
  39. 			}
  40. 			other.insert(temp);
  41. 			for(int j = 0; j < n; j++) {
  42. 				if(speaker == "?" and other.count(users[j])) continue;
  43. 				else if(speaker != "?" and speaker != users[j]) continue;
  44. 				if(i == 0) {
  45. 					memo[i][j] = j;	
  46. 					continue;
  47. 				}	
  48. 				for(int k = 0; k < n; k++) {
  49. 					if(k != j and memo[i - 1][k] != -1) {
  50. 						memo[i][j] = k;
  51. 						break;
  52. 					}
  53. 				}
  54. 			}
  55. 		}
  56. 		vector<string> result(m);
  57. 		int cU = -1;
  58. 		for(int j = 0; j < n; j++) {
  59. 			if(memo[m - 1][j] != -1) {
  60. 				cU = j;
  61. 				break;
  62. 			}
  63. 		}
  64. 		if(cU == -1) {
  65. 			cout << "Impossible" << endl;
  66. 		}
  67. 		else {
  68. 			result[m - 1] = users[cU] + messages[m - 1];
  69. 			for(int i = m - 2; i >= 0; i--) {
  70. 				cU = memo[i + 1][cU];
  71. 				result[i] = users[cU] + messages[i];
  72. 			}
  73. 			for(int i = 0; i < m; i++)
  74. 				cout << result[i] << endl;
  75. 		}
  76. 	}
  77. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
2
3
netman vladik Fedosik
2
?: users are netman, vladik, Fedosik
vladik: something wrong with this chat
4
netman tigerrrrr banany2001 klinchuh
4
?: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready?
klinchuh: yes, coach!
?: yes, netman
banany2001: yes of course.
stdout
copy 
Impossible
netman: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready?
klinchuh: yes, coach!
tigerrrrr: yes, netman
banany2001: yes of course.
https://ideone.com/6lOBdG
language:
C++14 (gcc 8.3)
created:
6 years 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!