Guest User

Untitled

a guest
Jul 18th, 2012
1,146
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #include <cstring>
  11. #include <cstdlib>
  12. #include <cmath>
  13. #include <string>
  14. #include <memory.h>
  15. #include <sstream>
  16. #include <ctime>
  17. #include <Windows.h>
  18. using namespace std;
  19.  
  20. #pragma comment(linker, "/stack:64000000")
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24. typedef pair<int, int> ii;
  25.  
  26. typedef vector<int> vi;
  27. typedef vector<pair<int, int > > vii;
  28. typedef vector<ll> vll;
  29. typedef vector<string> vs;
  30. typedef vector<ld> vld;
  31.  
  32. typedef vector<vi> vvi;
  33. typedef vector<vii> vvii;
  34. typedef vector<vll> vvll;
  35. typedef vector<vs> vvs;
  36.  
  37. typedef map<int, int> mpii;
  38. typedef map<int, string> mpis;
  39. typedef map<string, int> mpsi;
  40. typedef map<string, string> mpss;
  41.  
  42. #define all(a) (a).begin(),(a).end()
  43. #define rall(a) (a).rbegin(),(a).rend()
  44. #define sz(a) (int)((a).size())
  45. #define len(a) (int)((a).length())
  46.  
  47. #define forr(i,n) for (int i = 0; i < (n); ++i)
  48. #define fori(n) forr(i,n)
  49. #define forj(n) forr(j,n)
  50. #define fork(n) forr(k,n)
  51. #define forin fori(n)
  52. #define forjn forj(n)
  53. #define forjm forj(m)
  54. #define forkm fork(m)
  55. #define foria(a) fori(sz(a))
  56. #define foriv foria(v)
  57. #define foris fori(len(s))
  58. #define forja(a) forj(sz(a))
  59. #define forjv forj(v)
  60. #define forjs forj(len(s))
  61.  
  62. #define read cin>>
  63. #define write cout<<
  64. #define writeln write endl
  65.  
  66. #define readt int aaa; read aaa;
  67. #define gett (bbb+1)
  68. #define fort forr(bbb,aaa)
  69.  
  70. #define issa(a,s) istringstream a(s);
  71. #define iss(s) issa(ss,s);
  72.  
  73. ld dis(ld x, ld y) {return sqrt(x*x+y*y);}
  74. const ld PI = acos(ld(0.0))*2;
  75. const ld pi = PI;
  76.  
  77. ll gcd(ll a, ll b){return b ? gcd(b,a%b) : a;}
  78.  
  79. template<class T>
  80. struct makev
  81. {
  82. vector<T> v;
  83. makev& operator << (const T& x)
  84. {
  85. v.push_back(x);
  86. return *this;
  87. }
  88. operator vector<T>& ()
  89. {
  90. return v;
  91. }
  92. };
  93.  
  94. //void assert(bool b)
  95. //{
  96. // if (!b)
  97. // throw 0;
  98. //}
  99.  
  100. pair<string, string> hackHashInit()
  101. {
  102. return pair<string, string>("a", "b");
  103. }
  104.  
  105. ll getHash(const string &s, ll a, ll p)
  106. {
  107. ll res = 0;
  108. foris res = (res * a + s[i]) % p;
  109. return res;
  110. }
  111.  
  112. bool hackHash(pair<string, string> v, pair<string, string> &ans, ll a, ll p)
  113. {
  114. const int len = 22;
  115. map<ll, string> mp;
  116.  
  117. fori((1<<len))
  118. {
  119. string s;
  120. s.reserve(len * v.first.length());
  121. forj(len)
  122. if (i & (1 << j))
  123. s += v.first;
  124. else
  125. s += v.second;
  126.  
  127. ll h = getHash(s, a, p);
  128. if (mp.find(h) != mp.end())
  129. {
  130. ans.first = mp[h];
  131. ans.second = s;
  132. return true;
  133. }
  134.  
  135. mp.insert(make_pair(h, s));
  136. }
  137. return false;
  138. }
  139.  
  140. int main()
  141. {
  142. #ifdef _MSC_VER
  143. //freopen("input.txt", "rt", stdin);
  144. //freopen("output.txt", "wt", stdout);
  145. ifstream cin("input.txt");
  146. ofstream cout("output.txt");
  147. #else
  148. //ifstream cin("input.txt");
  149. //ofstream cout("output.txt");
  150. #endif
  151.  
  152. pair<string, string> collision;
  153. if (!hackHash(hackHashInit(), collision, 51, 1000000007))
  154. {
  155. cout << "FAIL!";
  156. return 0;
  157. }
  158. std::cout << "First OK!";
  159. if (!hackHash(collision, collision, 59, 1000000009))
  160. {
  161. cout << "FAIL!";
  162. return 0;
  163. }
  164.  
  165. cout << collision.first << endl;
  166. cout << getHash(collision.first, 51, 1000000007) << endl;
  167. cout << getHash(collision.first, 59, 1000000009) << endl;
  168.  
  169. cout << collision.second << endl;
  170. cout << getHash(collision.second, 51, 1000000007) << endl;
  171. cout << getHash(collision.second, 59, 1000000009) << endl;
  172.  
  173. return 0;
  174. }
RAW Paste Data