Advertisement
Guest User

Untitled

a guest
Feb 21st, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.17 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. #define ld long double
  4. #define pnode node*
  5.  
  6. typedef long long ll;
  7.  
  8. using namespace std;
  9.  
  10. ll n;
  11. string s, t;
  12. vector < ll > cnts(1000), cntt(1000);
  13.  
  14.  
  15. void no(){
  16. cout << -1 << "\n";
  17. exit(0);
  18. }
  19.  
  20. vector < ll > ans;
  21.  
  22.  
  23. void mv(ll pos){
  24. if(pos == n)return;
  25. ll len = (n - 1) - pos + 1;
  26. ans.push_back(len);
  27. string cs = "";
  28. for(ll i = n - 1; i >= pos; --i){
  29. cs.push_back(s[i]);
  30. }
  31. for(ll i = 0; i < pos; ++i){
  32. cs.push_back(s[i]);
  33. }
  34. s = cs;
  35. }
  36.  
  37. ll find_pref(char a){
  38. for(ll i = 0; i < n; ++i){
  39. if(s[i] == a){
  40. return i;
  41. }
  42. }
  43. assert(0);
  44. }
  45.  
  46. ll find_suff(char a){
  47. for(ll i = n - 1; i >= 0; --i){
  48. if(s[i] == a){
  49. return i;
  50. }
  51. }
  52. assert(0);
  53. }
  54.  
  55.  
  56.  
  57.  
  58.  
  59. void solve(){
  60. cin >> n;
  61. cin >> s >> t;
  62. for(ll i = 0; i < n; ++i){
  63. cnts[s[i]]++;
  64. cntt[t[i]]++;
  65. }
  66. for(ll i = 0; i < 1000; ++i){
  67. if(cnts[i] != cntt[i]){
  68. no();
  69. }
  70. }
  71. ll pos = n / 2;
  72. char cur = t[pos];
  73. ll spos = find_pref(cur);
  74. mv(spos + 1);
  75. bool rev = 0;
  76. cerr << s << " " << t << "\n";
  77. for(ll i = 1; i <= n; ++i){
  78. ll posl = pos - i;
  79. ll posr = pos + i;
  80. if(posl < 0 || posr >= n)break;
  81. if(!rev)swap(posl, posr);
  82. ll CSZ = 2 * (i - 1) + 1;
  83. ll fposl = find_pref(t[posl]);
  84. mv(fposl + 1);
  85. mv(0);
  86. mv(n - CSZ);
  87. ll fposr = find_suff(t[posr]);
  88. ll BSZ = n - fposr - 1;
  89. ll ASZ = fposr - CSZ - 1;
  90. mv(n - BSZ - 1);
  91. mv(n - ASZ);
  92. rev ^= 1;
  93. cerr << s << "\n";
  94. cerr << t << "\n";
  95. cerr << "\n\n";
  96. }
  97. cout << s << "\n";
  98. cout << t << "\n";
  99. }
  100.  
  101. signed main(){
  102. ll t = 1;
  103. srand(time(0));
  104. cout << fixed << setprecision(20);
  105. ios_base::sync_with_stdio(0);
  106. cin.tie(0);
  107. cout.tie(0);
  108. #ifdef DEBUG
  109. freopen("input.txt", "r", stdin);
  110. freopen("output.txt", "w", stdout);
  111. #else
  112.  
  113. #endif
  114. while(t--){
  115. solve();
  116. }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement