fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 50001; typedef long long ll; int n; int a[ N ]; ll ans[ 2 ][ N ];
  6.  
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10.  
  11. typedef pair<int,int> pii;
  12.  
  13. ll tme; int ner, idx, ls, val, k, it, BITree[ N + 1 ];
  14.  
  15. /// Updates a node in Binary Index Tree (BITree) at given index
  16. /// in BITree. The given value 'val' is added to BITree[i] and
  17. /// all of its ancestors in tree.
  18. /// Source: https://w...content-available-to-author-only...s.org/binary-indexed-tree-or-fenwick-tree-2/
  19.  
  20. void BITupdate( int index, int val, int n )
  21. {
  22.     /// index in BITree[] is 1 more than the index in arr[]
  23.  
  24.     index++;
  25.  
  26.     /// Traverse all ancestors and add 'val'
  27.  
  28.     while ( index <= n )
  29.     {
  30.         /// Add 'val' to current node of BI Tree
  31.  
  32.         BITree[ index ] += val;
  33.  
  34.         /// Update index to that of parent in update View
  35.  
  36.         index += index & (-index);
  37.     }
  38. }
  39.  
  40. /// Returns sum of arr[0..index]. This function assumes
  41. /// that the array is preprocessed and partial sums of
  42. /// array elements are stored in BITree[].
  43.  
  44. int BITquery( int index )
  45. {
  46.     int sum = 0; /// Initialize result
  47.  
  48.     /// index in BITree[] is 1 more than the index in arr[]
  49.  
  50.     index++;
  51.  
  52.     /// Traverse ancestors of BITree[index]
  53.  
  54.     while( index > 0 )
  55.     {
  56.         /// Add current element of BITree to sum
  57.  
  58.         sum += BITree[ index ];
  59.  
  60.         // Move index to parent node in getSum View
  61.         index -= index & (-index);
  62.     }
  63.  
  64.     return sum;
  65. }
  66. void solution1()
  67. {
  68.     vector<pii> arr;
  69.  
  70.     for( int j = 0, i = 1; i <= n; j = i++ )
  71.     {
  72.         arr.pb({a[ j ],i});
  73.  
  74.         /*  update the i-th index that it is initially present and the i-th
  75.             task has not been completed
  76.                 1-not completed
  77.                 0-completed
  78.         */
  79.  
  80.         BITupdate( i, 1, n );
  81.     }
  82.  
  83.     /// sorting in increasing order
  84.  
  85.     sort( arr.begin() , arr.end() );
  86.  
  87. 	for( int i = 0 ; i < n ; i++)
  88. 	{
  89. 		val = arr[i].fi;
  90. 		idx = arr[i].se;
  91. 		/// ner :- number of elements(tasks) remaining
  92. 		ner = n-i;
  93. 		/* find out number of task before current task which are not completed in the original array */
  94. 		ls = BITquery( idx );
  95.  
  96. 		/*  iteration required to make the current task zero = value of the task
  97.             so if the iteration is not the 1 less than val then we need to make it
  98.             come to iteration 1 less than the iteration required
  99.             eg:- val - 5 , it = 2 , then we make it = 4 by adding ner*(5-2-1) = ner*4
  100. 		*/
  101. 		if( val-1 > it )
  102. 		{
  103. 			tme += (val - 1 - it)*1ll*ner ;
  104. 		}
  105. 		/*  in tme add the position of the current element
  106.             after considering how many task has been done.
  107.         */
  108. 		ans[0][idx] = ls + tme;
  109.  
  110. 		/*  k is for counting how many elements have same value as the current element */
  111. 		k = 0;
  112. 		for( int j = i+1 ; j < n ; j++)
  113. 		{
  114. 			if( val == arr[j].fi )
  115. 			{
  116.                 /*  if element has same value then it's iteration will be equal
  117.                     to the iteration of current element
  118.                     then just add the position of the task in tme to get it's answer
  119.                 */
  120.                 ls = BITquery( arr[j].se );
  121.                 k++;
  122.                 ans[0][arr[j].se] = tme + ls;
  123.  
  124. 			}
  125. 			else
  126. 			{
  127. 				break;
  128. 			}
  129. 		}
  130.  
  131. 		for( int j = i ; j < n ; j++)
  132. 		{
  133. 			if( val != arr[j].fi )
  134. 			{
  135. 				break;
  136. 			}
  137. 			/*  updating values to -1 because the task have been completed
  138.                 and won't be considered in next iteration */
  139. 			BITupdate( idx, -1, n );
  140. 		}
  141. 		/*  make iteration equal to current value , similar update tme
  142.             for representing time past till current iteration and update i
  143.         */
  144. 		tme += ner;
  145. 		it = val;
  146. 		i = i+k;
  147.  
  148. 	}
  149.  
  150.     tme = 0, memset( BITree, 0, sizeof BITree ); // reset tme and bit
  151. }
  152.  
  153. void solution2()
  154. {
  155.     struct pending_tasks_t: vector< int >
  156.     {
  157.         int rank( int i )
  158.         {
  159.             return lower_bound( begin(), end(), i ) - begin();
  160.         }
  161.  
  162.         void remove_task( int i )
  163.         {
  164.             erase( lower_bound( begin(), end(), i ) );
  165.         }
  166.  
  167.     } p; ll time = n; vector< pair< int, int > > task;
  168.  
  169.     for( int i = 0, j = 1; i < n; i = j++ )
  170.         if ( a[ i ] == 1 )
  171.             ans[ 1 ][ j ] = j;
  172.         else
  173.             task.emplace_back( a[ i ], j ), p.push_back( j );
  174.  
  175.     sort( task.begin(), task.end() );
  176.  
  177. 	for( int i = 0, it = 2, k = 0, m = task.size(), remaining = m, t; i < m; i += k, it = t + 1, k = 0 )
  178.     {
  179.         time += ( ( t = task[ i ].first ) - it ) * ll( remaining ) + 1;
  180.  
  181. 		for( int j = i, q; j < m and task[ j ].first == t; j++, k++ )
  182.             q = task[ j ].second, ans[ 1 ][ q ] = time + p.rank( q );
  183.  
  184. 		for( int j = 0; j < k; j++ )
  185.             p.remove_task( task[ i + j ].second );
  186.  
  187.         time += remaining - 1, remaining -= k;
  188. 	}
  189. }
  190.  
  191. inline void write_solution( int i )
  192. {
  193.     const string eos = " \n";
  194.  
  195.     for( int j = 1; j <= n; j++ )
  196.         cout << ans[ i ][ j ] << eos[ j < n ];
  197. }
  198.  
  199. void write_counterexample( uint64_t seed, int test_cases )
  200. {
  201.     cout << endl << test_cases << " random test case(s) generated." << endl;
  202.  
  203.     cout << endl << "random number generator seed: " << seed << endl;
  204.  
  205.     cout << endl << "A counterexample was found with different answers:";
  206.  
  207.     for( int i = 0; i < n; i++ )
  208.         cout << ' ' << a[ i ];
  209.  
  210.     cout << endl;
  211.  
  212.     for( int i = 0, j = 1; i < 2; i = j++ )
  213.         cout << endl << "solution " << j << ": ", write_solution( i ), cout << endl;
  214. }
  215.  
  216. int main()
  217. {
  218.     int random; cin >> random;
  219.  
  220.     if ( random )
  221.     {
  222.         int max_time, max_tests; uint64_t seed; cin >> n >> max_time >> max_tests >> seed;
  223.  
  224.         assert( n > 0 and n < N and max_time > 0 and max_tests > 0 );
  225.  
  226.         if ( seed == 0 )
  227.             seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  228.  
  229.         bool found = false; int test_cases = 0;
  230.  
  231.         for( mt19937_64 random_number_generator( seed ); not found and test_cases < max_tests; test_cases++ )
  232.         {
  233.             for( int i = 0; i < n; i++ )
  234.                 a[ i ] = 1 + random_number_generator() % max_time;
  235.  
  236.             solution1(),
  237.             solution2();
  238.  
  239.             for( int i = 1; i <= n and not found; i++ )
  240.                 if ( ans[ 0 ][ i ] != ans[ 1 ][ i ] )
  241.                     found = true;
  242.         }
  243.  
  244.         if ( found )
  245.             write_counterexample( seed, test_cases );
  246.         else
  247.             cout << "No counterexample was found";
  248.     }
  249.     else
  250.     {
  251.         const function< void() > f[] = { solution1, solution2 };
  252.  
  253.         int solution; cin >> solution >> n;
  254.  
  255.         solution--, assert( ( solution == 0 or solution == 1 ) and ( n > 0 and n < N ) );
  256.  
  257.         for( int i = 0; i < n; i++ )
  258.             cin >> a[ i ];
  259.  
  260.         f[ solution ](), write_solution( solution );
  261.     }
  262. }
  263.  
Success #stdin #stdout 0s 16416KB
comments (?)
stdin
copy 
0 2 10
6 10 1 7 6 10 1 10 2 1
stdout
copy 
36
52
3
43
39
53
7
54
17
10
https://ideone.com/Idipw6
Counterexample
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!