Advertisement
Guest User

Untitled

a guest
Dec 17th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.79 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:167772160000")
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <fstream>
  6. #include <stdio.h>
  7. #include <cstdio>
  8. #include <stdlib.h>
  9. #include <cstdlib>
  10. #include <algorithm>
  11. #include <cstring>
  12. #include <string>
  13. #include <vector>
  14. #include <list>
  15. #include <stack>
  16. #include <climits>
  17. #include <set>
  18. #include <bitset>
  19. #include <math.h>
  20. #include <queue>
  21. #include <map>
  22. #include <sstream>
  23. #include <functional>
  24. #include <assert.h>
  25. #include <unordered_map>
  26. #include <unordered_set>
  27. #include <complex>
  28.  
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef long double ld;
  32. typedef std::pair<int, int> pii;
  33. typedef std::pair<double, double> pdd;
  34. template <typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
  35. template <typename T> using max_heap = std::priority_queue<T, std::vector<T>, std::less<T>>;
  36.  
  37. #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);
  38. #define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++)
  39. #define FOR(i, start, end) for(int i = (start); i < (end); i++)
  40. #define ROF(i, start, end) for(int i = (start); i >= (end); i--)
  41. #define all(x) (x).begin(), (x).end()
  42. //#define endl "\n"
  43. #define PI (asin(1)*2)
  44. #define OO ((1LL<<31)-1)
  45. #define eps 1e-12
  46. #define in(a, b) ((b).find(a) != (b).end())
  47. #define mp(a, b) make_pair((a), (b))
  48. #define sgn(a) ((a) > eps ? 1 : ((a) < -eps ? -1 : 0))
  49. #define cl1(x) ((x)&((x)-1)) // clear lowest 1 bit
  50. #define cl0(x) ((x)|((x)+1)) // clear lowest 0 bit
  51. #define ct1(x) ((x)&((x)+1)) // clear all trailing 1 bits
  52. #define pb push_back
  53. #define MOD 1000000007
  54. #define MAX_N 1000000
  55. using namespace std;
  56.  
  57. string signs = "";
  58. set<char> letters;
  59. int din[50];
  60. int dout[50];
  61. bool connected[50][50];
  62. vector<int> neigh[50];
  63.  
  64. bool isGood(const string& s) {
  65. for (auto c : letters) {
  66. din[c - 'a'] = dout[c - 'a'] = 0;
  67. neigh[c - 'a'].clear();
  68. for (auto cc : letters) connected[c - 'a'][cc - 'a'] = false;
  69. }
  70. FOR(i, 0, signs.length()) {
  71. int bef = s[i] - 'a';
  72. int aft = s[i + 1] - 'a';
  73. if (signs[i] == '<') {
  74. if (!connected[aft][bef]) {
  75. din[bef]++;
  76. dout[aft]++;
  77. neigh[aft].pb(bef);
  78. connected[aft][bef] = true;
  79. }
  80. }
  81. else if (signs[i] == '>') {
  82. if (!connected[bef][aft]) {
  83. dout[bef]++;
  84. din[aft]++;
  85. neigh[bef].pb(aft);
  86. connected[bef][aft] = true;
  87. }
  88. }
  89. }
  90. stack<int> S;
  91. for (auto c : letters) {
  92. if (din[c-'a'] == 0) {
  93. S.push(c-'a');
  94. }
  95. }
  96. int cnt = 0;
  97. while (!S.empty()) {
  98. if (S.size() > 1) {
  99. return false;
  100. }
  101. int top = S.top(); S.pop();
  102. for (auto n : neigh[top]) {
  103. din[n]--;
  104. if (din[n] == 0) S.push(n);
  105. }
  106. cnt++;
  107. }
  108. return cnt == letters.size();
  109. }
  110.  
  111. void buildSigns(const string& s, int idx) {
  112. if (idx == s.length() - 1) {
  113. // check
  114. if (isGood(s)) {
  115. FOR(i, 0, signs.length()) {
  116. cout << s[i] << " " << signs[i] << " ";
  117. }
  118. cout << s[s.length() - 1] << endl;
  119. exit(0);
  120. }
  121. return;
  122. }
  123. if (s[idx] == s[idx + 1]) {
  124. signs[idx] = '=';
  125. buildSigns(s, idx + 1);
  126. return;
  127. }
  128. int bef = s[idx] - 'a';
  129. int aft = s[idx + 1] - 'a';
  130.  
  131. if (!connected[aft][bef]) {
  132. signs[idx] = '>';
  133. connected[bef][aft] = true;
  134. buildSigns(s, idx + 1);
  135. connected[bef][aft] = false;
  136. }
  137.  
  138. if (!connected[bef][aft]) {
  139. connected[aft][bef] = true;
  140. signs[idx] = '<';
  141. buildSigns(s, idx + 1);
  142. connected[aft][bef] = false;
  143. }
  144. }
  145.  
  146. int main()
  147. {
  148. FAST_IO
  149. #ifdef _DEBUG
  150. freopen("input.txt", "r", stdin);
  151. freopen("output.txt", "w", stdout);
  152. #endif
  153. string s;
  154. cin >> s;
  155. for (char c : s) {
  156. signs += " ";
  157. letters.insert(c);
  158. }
  159. signs = signs.substr(0, signs.length() - 1);
  160. buildSigns(s, 0);
  161. cout << "Impossible" << endl;
  162. return 0;
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement