fork download
copy 
  1.  
  2.  
  3. #ifdef Asaad
  4.     #include "cp.h"
  5.     #define debug(...) _dbg_many(#__VA_ARGS__, __VA_ARGS__)
  6.     #define here cerr << "LINE " << __LINE__ << "\n"
  7. #else 
  8.     #include <bits/stdc++.h>
  9.     using namespace std;
  10.     /*
  11.     #include <ext/pb_ds/assoc_container.hpp>
  12.     #include <ext/pb_ds/tree_policy.hpp>
  13.     using namespace __gnu_pbds;
  14.     template<class T>
  15.     using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  16.     */
  17.     #define debug(...) 
  18.     #define here 
  19. #endif
  20.  
  21.  
  22.  
  23. #define ll long long
  24. #define int long long
  25. #define all(x) x.begin(), x.end()
  26. #define siz(x) ((int)x.size())
  27. #define yes cout << "YES\n"
  28. #define no cout << "NO\n"
  29. #define f first
  30. #define s second
  31. #define eb emplace_back
  32. #define pb push_back
  33.  
  34.  
  35. const int mod = 1e9+7;
  36. const int N = 200009;
  37. const long long inf = 1e18+12309138;
  38. double eps = 1e-9;
  39.  
  40. mt19937 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
  41.  
  42. int rnd(int l, int r) {
  43.     return uniform_int_distribution<int>(l, r)(rng);
  44. }
  45.  
  46.  
  47. pair<int, int> slow ( int x, int y, int w ) {
  48.     set<int> nx, ny;
  49.     int box = 0, c = 0;
  50.     while ( x+y > 0 ) {
  51.         if ( x >= y ) {
  52.             x--;
  53.             nx.insert(box);
  54.         } else {
  55.             y--;
  56.             ny.insert(box);
  57.         }
  58.         c++;
  59.         if ( c == w ) {
  60.             c = 0;
  61.             box++;
  62.         }
  63.     }
  64.     return { siz(nx), siz(ny) };
  65.  
  66. } 
  67.  
  68. pair<int, int> As3ad ( int x, int y, int w ) {
  69.  
  70.     int ans[2] = {0};
  71.     if ( w == 1 ) {
  72.         return {x, y};
  73.     }
  74.     bool p = 0;
  75.     bool big = ( x < y );
  76.     int dif = abs(x-y);
  77.     ans[big] += (dif+w-1)/w;
  78.     int tot = min(x, y)*2;
  79.     int rem = (w-(dif%w))%w;
  80.     if ( rem > 0 ) {
  81.         if ( big && (tot>0) ) ans[0]++;
  82.         else if ( rem > 1  && (tot>1) ) ans[1]++;
  83.         p^=rem%2; 
  84.         if ( tot <= rem ) {
  85.             return { ans[0], ans[1] };
  86.         }
  87.         tot-= rem;
  88.     }
  89.     ans[0] += tot/w;
  90.     ans[1] += tot/w;
  91.     p^=((tot/w)*w)%2;
  92.     tot-= (tot/w)*w;
  93.     if ( tot > 0 ) ans[p]++;
  94.     if ( tot > 1 ) ans[p^1]++;
  95.  
  96.     return { ans[0], ans[1] };
  97. }
  98.  
  99. void ch ( int x, int y, int w ) {
  100.     pair<int, int> correct = slow(x, y, w);
  101.     pair<int, int> asaad = As3ad( x, y, w );
  102.     if ( asaad != correct ) {
  103.         cout << "BAD ... \n";
  104.         cout << "x: " << x << "\n"; 
  105.         cout << "y: " << y << "\n"; 
  106.         cout << "w: " << w << "\n"; 
  107.         cout << "Correct: " << correct.f << " " << correct.s << "\n";
  108.         cout << "yours ): " << asaad.f << " " << asaad.s << "\n";
  109.         exit(0);
  110.     }
  111. }
  112.  
  113.  
  114. void tc () {
  115.     //nb=
  116.  
  117.     for (int x=0; x<100; x++) {
  118.         for (int y=0; y<100; y++) {
  119.             for (int w = 1; w<100; w++) {
  120.                 ch(x, y, w);
  121.             }
  122.         }
  123.     }
  124.     for (int i=0; i<1000; i++) {
  125.         int x = rnd( 0, 1e5 );
  126.         int y = rnd( 0, 1e5 );
  127.         int w = rnd( 1, 1e5 );
  128.         ch(x, y, w);
  129.  
  130.     }
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138. } 
  139.  
  140.  
  141.  
  142.  
  143.  
  144. signed main () { 
  145.     ios::sync_with_stdio(false);
  146.     cin.tie(0);
  147.     //freopen( "input.txt", "r", stdin );
  148.     //freopen( "output.txt", "w", stdout );
  149.     //cout << fixed << setprecision(9);
  150.     //pre();
  151.     int t=1;
  152.     //cin >> t;
  153.  
  154.     for (int i=1; i<=t; i++) {
  155.         #ifdef Asaad
  156.             auto start = chrono::high_resolution_clock::now();
  157.             //cout << "---Case " << i << " Start---\n\n";
  158.         #endif
  159.  
  160.         tc();
  161.  
  162.  
  163.         #ifdef Asaad
  164.             auto end = chrono::high_resolution_clock::now();
  165.             //cout << "---Case " << i << " End---\n";
  166.             //if ( i%100000 == 0 )
  167.             cerr << "Time #" << i << ": " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms" << endl;
  168.             //cout << "--------------\n";
  169.         #endif
  170.     }
  171.     cout << "ALL good\n";
  172. }
  173.  
  174.  
  175.  
  176.  
Success #stdin #stdout 1.89s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ALL good
https://ideone.com/er8bzh
proof of correctness (shipping boxes)
language:
C++14 (gcc 8.3)
created:
21 hours 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!