SHARE
TWEET

Untitled

a guest Jul 18th, 2012 851 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top