Advertisement
GerONSo

Untitled

Nov 23rd, 2019
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10.  
  11.  
  12. // #pragma GCC optimize("O3")
  13. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  14.  
  15. #include <bits/stdc++.h>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. #define ll long long
  20. #define all(x) begin(x), end(x)
  21. #define x first
  22. #define y second
  23. #define int long long
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef long double ld;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(14);
  39. #ifdef _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e6 + 10;
  46. const int MAXM = 600;
  47. const int INF = 1e9;
  48. const int BASE = 47;
  49. const int MOD = 1e9 + 7;
  50. const int MAXLOG = 21;
  51. const ld EPS = 1e-6;
  52.  
  53. vector<int> pw;
  54.  
  55. int get_hash(string s) {
  56. int h = 0;
  57. for(int i = 0; i < s.size(); i++) {
  58. h += s[i] * pw[i];
  59. h %= MOD;
  60. }
  61. return h;
  62. }
  63.  
  64. signed main() {
  65. seriy();
  66. int n;
  67. cin >> n;
  68. pw.resize(MAXN);
  69. pw[0] = 1;
  70. for(int i = 1; i < MAXN; i++) {
  71. pw[i] = pw[i - 1] * BASE;
  72. pw[i] %= MOD;
  73. }
  74. string s, t;
  75. cin >> s >> t;
  76. int c = INF, f = INF;
  77. for(auto i : s) {
  78. c = min(c, (int)(i - 'a'));
  79. }
  80. for(auto i : t) {
  81. f = min(f, (int)(i - 'a'));
  82. }
  83. for(int i = 0; i < n; i++) {
  84. s[i] -= c;
  85. t[i] -= f;
  86. }
  87. int h = get_hash(s);
  88. int g = get_hash(t);
  89. for(int i = n - 1; i >= 0; i--) {
  90. g = (g - t[i] * pw[n - 1] + MOD * MOD) % MOD;
  91. g *= BASE;
  92. g %= MOD;
  93. g += t[i];
  94. g %= MOD;
  95. if(g == h) {
  96. cout << "Success\n";
  97. cout << i << " " << f - c << '\n';
  98. return 0;
  99. }
  100. }
  101. cout << "Impossible";
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement