fork(4) download
copy 
  1. /**
  2.  * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
  3.  * Date: 2012.12.22
  4.  */
  5.  
  6. #include <cstdio>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <iostream>
  10.  
  11. using namespace std;
  12.  
  13. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  14. #define pb push_back
  15.  
  16. typedef long long ll;
  17. typedef long double dbl;
  18.  
  19. inline ll mul( ll a, ll b, ll mod )
  20. {
  21.   ll k = (dbl)a * b / mod;
  22.   ll r = a * b - k * mod;
  23.   while (r < 0)
  24.     r += mod;
  25.   while (r >= mod)
  26.     r -= mod;
  27.   return r;
  28. }
  29.  
  30. struct tree
  31. {
  32.   ll val;
  33.   tree *l, *r;
  34.  
  35.   tree( ll _val, tree *_l, tree *_r ) : val(_val), l(_l), r(_r) { }
  36. };
  37.  
  38. typedef tree * ptree;
  39.  
  40. struct TreeComp
  41. {
  42.   bool operator () ( const ptree &a, const ptree &b )
  43.   {
  44.     return a->val < b->val;
  45.   }
  46. };
  47.  
  48. const int N = 10000;
  49.  
  50. int an;
  51. tree *a[N];
  52. char s[N + 1], t[N + 1];
  53.  
  54. void result( tree *a, int f )
  55. {
  56.   if (!a->r)
  57.   {
  58.     int i = (int)(a->l);
  59.     (f ? s : t)[N - i - 1]++;
  60.     return;
  61.   }
  62.   int swap = (a->l->val < a->r->val);
  63.   result(a->l, f ^ swap);
  64.   result(a->r, f ^ swap ^ 1);
  65. }
  66.  
  67. int main()
  68. {
  69.   #define NAME "breaking-hashing"
  70.   assert(freopen(NAME ".in", "r", stdin));
  71.   assert(freopen(NAME ".out", "w", stdout));
  72.  
  73.   ll p, q;
  74.   cin >> p >> q;
  75.  
  76.   ll f = 1;
  77.   forn(i, N)
  78.     a[an++] = new tree(f, (tree *)i, 0), f = mul(f, p, q);
  79.   while (an)
  80.   {
  81.     sort(a, a + an, TreeComp());
  82.     if (a[0]->val == 0)
  83.     {
  84.       forn(i, N)
  85.         s[i] = t[i] = 'a';
  86.       result(a[0], 0);
  87.       puts(s);
  88.       puts(t);
  89.       return 0;
  90.     }
  91.     forn(i, an / 2)
  92.       a[i] = new tree(abs(a[2 * i]->val - a[2 * i + 1]->val), a[2 * i], a[2 * i + 1]);
  93.     an /= 2;
  94.   }
  95.   puts("Impossible");  
  96.   return 0;
  97. }
  98.  
Runtime error #stdin #stdout #stderr 0s 3288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:70: int main(): Assertion `freopen("breaking-hashing" ".in", "r", stdin)' failed.
https://ideone.com/7fKYgQ
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!