fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define SELF_TEST
  6.  
  7. const int N = 2000, P = N + 1; int a[ N ][ N ];
  8.  
  9. typedef long long ll;  ll sum[ P ][ P ];
  10.  
  11. typedef long double ldbl;
  12.  
  13. typedef chrono::high_resolution_clock Clock_t;
  14.  
  15. typedef Clock_t::time_point      time_point_t;
  16.  
  17. time_point_t Now() { return Clock_t::now(); }
  18.  
  19. struct Timer_t
  20. {
  21.     time_point_t start_time;
  22.  
  23.     Timer_t() : start_time( Now() ) {}
  24.  
  25.     typedef long double ldbl;
  26.  
  27.     typedef chrono::nanoseconds nanosec_t;
  28.  
  29.     ll elaped_time()
  30.     {
  31.         nanosec_t timer = chrono::duration_cast< nanosec_t >( Now() - start_time );
  32.  
  33.         return timer.count();
  34.     }
  35. };
  36.  
  37. struct random_t: mt19937_64
  38. {
  39.     random_t() : mt19937_64( Clock_t::now().time_since_epoch().count() ) {}
  40.  
  41.     int random( int MIN, int MAX )
  42.     {
  43.         ll x_min = MIN, x_max = MAX, interval = x_max - x_min + 1, number = (*this)();
  44.  
  45.         if ( number < 0 )
  46.             number += LLONG_MAX;
  47.  
  48.         return x_min + ( number % interval );
  49.     }
  50.  
  51. } mt;
  52.  
  53. inline string time_to_str( const string &prefix, ll elapsed_time )
  54. {
  55.     return prefix + " time " + to_string( elapsed_time ) + " msec.";
  56. }
  57.  
  58. const string no_solution = "NIE";
  59.  
  60. struct plot_purchase_t
  61. {
  62.     ll elapsed_time, iterations, r, s, t; int test_case, k, l, n, a_min;
  63.  
  64.     void answer( Timer_t &timer, string solution )
  65.     {
  66. #ifdef SELF_TEST
  67.  
  68.         elapsed_time = timer.elaped_time() / 1000000LL,
  69.         solution  = "test " + to_string( test_case ) + ": " + solution,
  70.         solution += ", " + time_to_str( "elapsed", elapsed_time );
  71.  
  72. #endif
  73.  
  74.         cout << solution;
  75.  
  76. #ifdef SELF_TEST
  77.  
  78.         cout << endl;
  79.  
  80. #endif
  81.     }
  82.  
  83.     void solve()
  84.     {
  85.         Timer_t timer; int x0, y0, x1, y1, x2, y2;
  86.  
  87.         for( y0 = 0, y1 = 1; y0 < n; y0 = y1++ )
  88.             for( x0 = 0, x1 = 1; x0 < n; x0 = x1++ )
  89.             {
  90.                 auto &z = sum[ y1 ][ x1 ];
  91.  
  92.                 z  =   a[ y0 ][ x0 ],
  93.                 z += sum[ y0 ][ x1 ],
  94.                 z += sum[ y1 ][ x0 ],
  95.                 z -= sum[ y0 ][ x0 ];
  96.             }
  97.  
  98.  
  99.         if ( sum[ n ][ n ] < k or a_min > l )
  100.             return answer( timer, no_solution );
  101.  
  102.         if ( sum[ n ][ n ] <= l )
  103.             return answer( timer, "1 1 " + to_string( n ) + " " + to_string( n ) );
  104.  
  105.         for( y0 = 0, y1 = 1; y0 < n; y0 = y1++ )
  106.             for( x0 = 0, x1 = 1; x0 < n; x0 = x1++ )
  107.                 if ( a[ y0 ][ x0 ] <= l )
  108.                 {
  109.                     for( r = sum[ y0 ][ x0 ], y2 = y1; y2 <= n; y2++ )
  110.                         for( s = sum[ y2 ][ x0 ] - r, x2 = x1; x2 <= n; x2++ )
  111.                             if ( ( iterations++, t = sum[ y2 ][ x2 ] - sum[ y0 ][ x2 ] - s ) > l )
  112.                                 break;
  113.                             else
  114.                                 if ( t >= k )
  115.                                 {
  116.                                     string solution =   to_string( y1 ) + ' ' +
  117.                                                         to_string( x1 ) + ' ' +
  118.                                                         to_string( y2 ) + ' ' +
  119.                                                         to_string( x2 );
  120. #ifdef SELF_TEST
  121.                                     solution +=     "\nn = " +
  122.                                                     to_string( n ) + ", k = " +
  123.                                                     to_string( k ) + ", " +
  124.                                                     to_string( iterations ) + " iteration(s), sum / k = " +
  125.                                                     to_string( ldbl( t ) / ldbl( k ) );
  126. #endif
  127.                                     return answer( timer, solution );
  128.  
  129.                                 }
  130.                 }
  131.  
  132.             return answer( timer, no_solution );
  133.     }
  134.  
  135.     plot_purchase_t( int t = 0 ) :	elapsed_time( 0 ), iterations( 0 ),
  136. 			test_case( t ), a_min( INT_MAX )
  137.     {
  138.  
  139. #ifdef SELF_TEST
  140.  
  141.           k = mt.random( 1, 1000000000 ),
  142.           n = mt.random( 1, 2000 );
  143.  
  144.  
  145.         for( int y0 = 0; y0 < n; y0++ )
  146.             for( int x0 = 0; x0 < n; x0++ )
  147.                 a[ y0 ][ x0 ] = mt.random( 1, 2000000000 );
  148.  
  149.         a[ 1999 ][ 1999 ] = 200000001;
  150. #else
  151.  
  152.         cin >> k >> n;
  153.  
  154.         for( int y0 = 0; y0 < n; y0++ )
  155.             for( int x0 = 0; x0 < n; x0++ )
  156.                 cin >> a[ y0 ][ x0 ];
  157.  
  158. #endif
  159.  
  160.         memset( sum, 0, sizeof sum );
  161.  
  162.         for( int y0 = 0; y0 < n; y0++ )
  163.             for( int x0 = 0; x0 < n; x0++ )
  164.                 a_min = min( a_min, a[ y0 ][ x0 ] );
  165.  
  166.        l = 2 * k, solve();
  167.     }
  168.  
  169. };
  170.  
  171. template< typename T > struct data_analysis_t
  172. {
  173.     T min_value, max_value, sum; int count;
  174.  
  175.     data_analysis_t() : min_value( LLONG_MAX ), max_value( LLONG_MIN ),
  176.                         sum( 0 ), count( 0 ) {}
  177.  
  178.     void add_value( T x )
  179.     {
  180.         min_value = min( min_value, x ),
  181.         max_value = max( max_value, x ),
  182.         sum      += x,
  183.         count++;
  184.     }
  185.  
  186.     ldbl avg_value() const
  187.     {
  188.         return ldbl( sum ) / ldbl( count );
  189.     }
  190.  
  191.     friend ostream& operator << ( ostream &output, const data_analysis_t &x )
  192.     {
  193.         output << "avg " << ldbl( x.sum ) / ldbl( x.count ) << ", ",
  194.         output << "min " << x.min_value << ", ",
  195.         output << "max " << x.max_value;
  196.  
  197.         return output;
  198.     }
  199. };
  200.  
  201. int main()
  202. {
  203.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  204.  
  205. #ifdef SELF_TEST
  206.  
  207.     int tests; cin >> tests; assert( tests > 0 );
  208.  
  209.     data_analysis_t< ll > elapsed_time, iterations, n, k;
  210.  
  211.     data_analysis_t< ldbl > s;
  212.  
  213.     for( int i = 0; i < tests; i++ )
  214.     {
  215.         plot_purchase_t problem( i );
  216.  
  217.         elapsed_time.add_value( problem.elapsed_time ),
  218.           iterations.add_value( problem.iterations   ),
  219.                    n.add_value( problem.n            ),
  220.                    k.add_value( problem.k            ),
  221.                    s.add_value( ldbl( problem.t ) / ldbl( problem.k ) );
  222.     }
  223.  
  224.     cout << "elapsed time: " << elapsed_time << endl,
  225.     cout << "iteration(s): " << iterations << endl,
  226.     cout << "n           : " << n << endl,
  227.     cout << "k           : " << k << endl,
  228.     cout << "sum / k     : " << s << endl;
  229.  
  230. #else
  231.  
  232.     plot_purchase_t problem; problem.solve();
  233.  
  234. #endif
  235. }
  236.  
Success #stdin #stdout 0.11s 49576KB
comments (?)
stdin 
10
stdout 
test 0: 1 1 2 1
n = 769, k = 393825606, 3 iteration(s), sum / k = 1.934313, elapsed time 1 msec.
test 1: 1 7 1 7
n = 323, k = 363312108, 325 iteration(s), sum / k = 1.645742, elapsed time 0 msec.
test 2: 1 1 1 1
n = 57, k = 777295349, 1 iteration(s), sum / k = 1.886416, elapsed time 0 msec.
test 3: 1 2 1 2
n = 936, k = 651598796, 1 iteration(s), sum / k = 1.377248, elapsed time 2 msec.
test 4: 1 3 1 3
n = 475, k = 543468849, 477 iteration(s), sum / k = 1.395010, elapsed time 0 msec.
test 5: 1 11 1 11
n = 132, k = 119637833, 1 iteration(s), sum / k = 1.735845, elapsed time 0 msec.
test 6: 1 8 1 8
n = 1120, k = 155075975, 1 iteration(s), sum / k = 1.696990, elapsed time 3 msec.
test 7: 1 3 1 3
n = 1444, k = 194390918, 1 iteration(s), sum / k = 1.261075, elapsed time 4 msec.
test 8: 1 4 1 4
n = 414, k = 457467209, 1 iteration(s), sum / k = 1.711714, elapsed time 0 msec.
test 9: 1 1 1 2
n = 1921, k = 988840422, 2 iteration(s), sum / k = 1.147386, elapsed time 7 msec.
elapsed time: avg 1.7, min 0, max 7
iteration(s): avg 81.3, min 1, max 477
n           : avg 759.1, min 57, max 1921
k           : avg 4.64491e+08, min 119637833, max 988840422
sum / k     : avg 1.57917, min 1.14739, max 1.93431
https://ideone.com/F8Pyu8
Plot Purchase Self-Testing
language:
C++14 (gcc 8.3)
created:
6 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!