fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define display(arr,s,e) for(i=s; i<=e; i++) cout<<arr[i]<<" ";
  5. #define mset(arr,x) memset(arr,x,sizeof(arr))
  6.  
  7. # define MOD 4294967296
  8. #define epsilon 0.000000000001
  9. #define I_MAX 9223372036854775807
  10. #define I_MIN -9223372036854775807
  11.  
  12. #define rep(i,s,e) for(i=s;i<=e;i++)
  13. #define rrep(i,s,e) for(i=s;i>=e;i--)
  14. #define endl "\n"
  15.  
  16. #define ll long long
  17. #define mid(a,b) ((a)+((b-a)/2))
  18. #define min(a,b) ((a)<(b)?(a):(b))
  19. #define max(a,b) ((a)>(b)?(a):(b))
  20.  
  21. // Useful STL commands:
  22. #define pb push_back
  23. #define mp make_pair
  24. #define f first
  25. #define s second
  26. #define si set<int>
  27. #define vi vector<int>
  28. #define ii pair<int,int>
  29. #define sii set<ii>
  30. #define vii vector<ii>
  31. #define all(c) c.begin(),c.end()
  32. #define tr(c,it) for(auto it=c.begin();it!=c.end();++it)
  33.  
  34. #define DEBUG
  35. // debugging
  36. #ifdef DEBUG
  37. #define trace1(x)                    cerr << #x << ": " << x << endl;
  38. #define trace2(x, y)                 cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  39. #define trace3(x, y, z)              cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  40. #define trace4(a, b, c, d)           cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  41. #define trace5(a, b, c, d, e)        cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  42. #define trace6(a, b, c, d, e, f)     cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  43. #else
  44. #define trace1(x)
  45. #define trace2(x, y)
  46. #define trace3(x, y, z)
  47. #define trace4(a, b, c, d)
  48. #define trace5(a, b, c, d, e)
  49. #define trace6(a, b, c, d, e, f)
  50. #endif
  51.  
  52. double tick()
  53. {
  54.     static clock_t oldtick; clock_t newtick = clock();
  55.     double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
  56.     oldtick = newtick;
  57.     return diff;
  58. }
  59.  
  60. ll gcd(ll a, ll b)
  61. {
  62.     if( (a == 0) || (b == 0) )
  63.         return a + b;
  64.     return gcd(b, a % b);
  65. }
  66.  
  67. ll pow_mod(ll a, ll b)
  68. {
  69.     ll res = 1;
  70.     while(b)
  71.     {
  72.         if(b & 1)
  73.             res = (res * a)%MOD;
  74.         a = (a * a)%MOD;
  75.         b >>= 1;
  76.     }
  77.     return res;
  78. }
  79.  
  80. bool isPrime(ll a)
  81. {
  82.     for(int i=3; (i*i)<=a; i+=2)
  83.     {
  84.         if( (a%i)==0 )
  85.         {
  86.             return false;
  87.         }
  88.     }
  89.     if( ( a!=2 ) && ( (a%2)==0 ) )
  90.     {
  91.         return false;
  92.     }
  93.  
  94.     return true;
  95. }
  96.  
  97. string con_ll_to_str( ll a )
  98. {
  99.     stringstream mystr;
  100.     mystr << a;
  101.  
  102.     return mystr.str();
  103. }
  104.  
  105. ll con_str_to_ll( string st )
  106. {
  107.     ll numb = 0;
  108.     int len = st.size(), i, j = 0;
  109.     rrep(i, len-1, 0)
  110.     {
  111.        numb += ( pow_mod(10, j) * ( st[i] - '0' ) );
  112.        j++;
  113.     }
  114.  
  115.     return numb;
  116. }
  117.  
  118. // Remember that set and map have the member functions find() and count(), which works in O(log N).
  119. // tick() can be here or there so don't deter and submit it. Check it always on ideone.
  120.  
  121. // bitset<99999000000000>& c = *(new bitset<99999000000000>());   // For O(1) lookup the max bitset space required.
  122. ll arr[100010];
  123. bool flag;
  124. vector< pair< pair< ll, int > , bool > > vc;
  125. struct Compare {
  126.     bool operator() (const  pair< pair< ll, int > , bool >& pa1, const pair< pair< ll, int > , bool >& pa2 ) const
  127.     {
  128.         if( pa1.f.f==pa2.f.f )
  129.         {
  130.             return pa1.f.s < pa2.f.s;
  131.         }
  132.  
  133.         return pa1.f.f<pa2.f.f;
  134.     }
  135. };
  136.  
  137. int main()
  138. {
  139.     ios_base::sync_with_stdio(false);
  140.     cin.tie(0);
  141.  
  142.     int i, j, Q, turn = 0;
  143.     ll S1, A, B, Si, opop, ans = 0;
  144.  
  145.     cin >> Q >> S1 >> A >> B;
  146.  
  147.     Si = S1;
  148.     while( Q-- )
  149.     {
  150.         opop = Si/2;
  151.         if( Si&1 )
  152.         {
  153.            vc.pb( mp( mp(opop, turn), 1 ) );
  154.         }
  155.         else
  156.         {
  157.            vc.pb( mp( mp(opop, turn), 0 ) );
  158.         }
  159.  
  160.         Si = ( A*Si ) + B;
  161.         if( Si>=MOD )
  162.             Si %= MOD;
  163.  
  164.         turn++;
  165.     }
  166.     sort( all( vc ), Compare() );
  167.  
  168.     opop = I_MAX;
  169.     if( vc[0].s==1 )
  170.     {
  171.         opop = vc[0].f.f;
  172.         ans += opop;
  173.         flag = 1;
  174.     }
  175.     rep(i, 1, turn-1)
  176.     {
  177.         if( vc[i].f.f==opop && flag && vc[i].s==0 )
  178.         {
  179.             flag = 0;
  180.             ans -= vc[i].f.f;
  181.             opop = I_MAX;
  182.         }
  183.         else if( vc[i].f.f!=opop && vc[i].s==1 )
  184.         {
  185.             opop = vc[i].f.f;
  186.             ans += opop;
  187.             flag = 1;
  188.         }
  189.         else
  190.         {
  191.             opop = I_MAX;
  192.         }
  193.     }
  194.  
  195.     cout << ans;
  196.  
  197.  
  198.     cerr<<tick();
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout #stderr 3.6s 4364KB
comments (?)
stdin
copy 
10000000 777777777 777777777 777777777
stdout
copy 
5362358669068782
stderr
copy 
3.56754
https://ideone.com/ANL4Xo
language:
C++14 (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!