lib/Documentation/docs-sonyckson/1090.cpp

   1 /* mergesort :) con el contador :) en divide & conquer */
   2 #include <algorithm>
   3 #include <vector>
   4 #include <set>
   5 #include <string>
   6 #include <fstream>
   7 #include <iostream>
   8 #include <iomanip>
   9 #include <map>
  10 #include <stack>
  11 #include <sstream>
  12 #include <queue>
  13
  14 #include <cmath>
  15 #include <cstdio>
  16 #include <cctype>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <cassert>
  20 #define forn(i, n) for(int i=0;i<int(n);i++)
  21 #define foreach(it, c)  for(typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  22 #define ALL(x)   (x).begin(),(x).end()
  23 #define SORT(x) sort(ALL(x))
  24 using namespace std;
  25 #define VI vector<int>
  26 #define VS vector<string>
  27 #define PB push_back
  28 #define ll long long
  29
  30 int aux[10011];
  31 int caux[10011];
  32
  33
  34 int array[10011], cant[10011], c2[10011], a2[10011], a1[10011], c1[10011];
  35 void back(int b, int e){
  36         int i,j ,k;
  37         int n1,n2;
  38         if( e == b ){
  39                 cant[b] = 0;
  40                 return;
  41         }else if( e == b+1){
  42                 cant[b] = 0;
  43                 if( array[b] <= array[e] ){
  44                         cant[e] = 0;
  45                         swap(array[b], array[e]);
  46                 }else{
  47                         cant[b] = 0;
  48                         cant[e] = 1;
  49                 }
  50                 return;
  51         }
  52         back(b, (b+e)/2);
  53         back((b+e)/2+1, e);
  54         for(i=b;i<=(b+e)/2;i++)a1[i-b] = array[i], c1[i-b] = cant[i];
  55         n1 = (b+e)/2-b+1;
  56         for(i=(b+e)/2+1;i<=e;i++)a2[i-((b+e)/2+1)] = array[i], c2[i-((b+e)/2+1)] = cant[i];
  57         n2 = e-((b+e)/2+1)+1;
  58         a1[n1] = -1; a2[n2] = -1;
  59         int ind1 = 0, ind2 = 0;
  60         int cn = n1+n2;
  61         for(int h = 0 ; h < cn ; h ++ ){
  62                 if( a1[ind1] <= a2[ind2] ){
  63                         aux[h] = a2[ind2];
  64                         caux[h] = c2[ind2] + ind1 ;
  65                         ind2++;
  66                 }else{
  67                         aux[h] = a1[ind1];
  68                         caux[h] = c1[ind1];
  69                         ind1++;
  70                 }
  71         }
  72         for(i=b;i<=e;i++){
  73                 array[i] = aux[i-b];
  74                 cant[i] = caux[i-b];
  75         }
  76 }
  77 int main(){
  78         int i,j ,k, n;
  79         scanf("%i %i", &n, &k);
  80         int best = -1, nodo = -1;
  81         for(i=0;i<k;i++){
  82                 for(j=0;j<n;j++)scanf("%i", &array[j]);
  83                 back(0, n-1);
  84                 int total = 0;
  85                 for(j=0;j<n;j++)total += cant[j];
  86                 if( total > best ){ best = total, nodo = i;}
  87         }
  88         printf("%i\n", nodo+1);
  89         return 0;
  90 }