lib/Documentation/docs-sonyckson/3961.cpp

   1 // PROBLEMITA EN O ( N * SQRT ( N ) ) :) ASPERITO...
   2
   3 #include <algorithm>
   4 #include <vector>
   5 #include <set>
   6 #include <string>
   7 #include <fstream>
   8 #include <iostream>
   9 #include <iomanip>
  10 #include <map>
  11 #include <sstream>
  12 #include <queue>
  13
  14 #include <cmath>
  15 #include <cstdio>
  16 #include <cctype>
  17 #include <cstdlib>
  18 #include <cstring>
  19
  20 #define forn(i, n) for(int i=0;i<int(n);i++)
  21 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  22 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  23 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  24 #define ALL(x)   (x).begin(),(x).end()
  25 #define SIZE(x)   (int)(x).size()
  26 #define SORT(x) sort(ALL(x))
  27 using namespace std;
  28 #define VI vector<int>
  29 #define VS vector<string>
  30 #define PB push_back
  31 #define ISS istringstream
  32 #define OSS ostringstream
  33 #define MP make_pair
  34 typedef long long ll;
  35 int N;
  36 int res[100010], RES;
  37 int arr[100010];
  38 int pos[100010];
  39
  40 struct par{
  41         int first, second;
  42         par(){};
  43         par(int _x, int _y) {first=_x,second=_y;}
  44 };
  45
  46 struct par B2[100010];
  47 struct par B[100010];
  48 int indiceB;
  49 bool in(par p, int s){
  50         if( p.first <= s && s <= p.second ) return true;
  51         if( p.first >= s && s >= p.second ) return true;
  52         return false;
  53 }
  54 void change(int F, int SS){
  55         int i,j ,k;
  56         int S;
  57         int indiceB2=0;
  58         int R = F;
  59         int FI = 0;
  60         while( F > abs(B[FI].first-B[FI].second) ){
  61                 F -= 1+abs(B[FI].first-B[FI].second);
  62                 B2[indiceB2++] = par(B[FI].first, B[FI].second);
  63                 FI++;
  64         }
  65         if( F ){
  66                 if( B[FI].first < B[FI].second ){
  67                         B2[indiceB2++] = par(B[FI].first, B[FI].first+F-1);
  68                         B[FI].first = B[FI].first+F;
  69                 }else{
  70                         B2[indiceB2++] = par(B[FI].first, B[FI].first-F+1);
  71                         B[FI].first = B[FI].first-F;
  72                 }
  73                 F  = 0;
  74         }
  75         int ind = FI;
  76         while(1){
  77                 if( in(B[ind],SS) )break;
  78                 R += 1+abs(B[ind].first-B[ind].second);
  79                 ind++;
  80         }
  81         R--;
  82         if( B[ind].first < B[ind].second ) R += (SS-B[ind].first+1);
  83         else R += B[ind].first-SS+1;
  84         pair<int,int> agregar(-1,-1);
  85         if( B[ind].first < B[ind].second  && SS != B[ind].second ){
  86                 agregar.first = SS+1;agregar.second = B[ind].second;
  87                 B[ind].second = SS;
  88         }else if( B[ind].second < B[ind].first && SS != B[ind].second ){
  89                 agregar.first = SS-1; agregar.second = B[ind].second;
  90                 B[ind].second = SS;
  91         }
  92         for(i=0;i<(1+ind-FI)/2;i++)swap(B[i+FI],B[ind-i]);
  93         for(i=0;i<ind-FI+1;i++) B2[indiceB2++] = par(B[i+FI].second,B[i+FI].first);
  94         if( agregar.first != -1 ) B2[indiceB2++] = par(agregar.first, agregar.second);
  95         for(i=ind+1;i<indiceB;i++) B2[indiceB2++] = par(B[i].first, B[i].second);
  96 //      for(i=0;i<indiceB2;i++) B[i].first = B2[i].first, B[i].second = B2[i].second;
  97         memcpy(B,B2,sizeof(B[0])*indiceB2);
  98         indiceB = indiceB2;
  99         res[RES++] = R;
 100 }
 101 #define M 100010
 102 int arr1[M], pos1[M];
 103 void stable(){
 104         int i,j ,k;
 105         for(i=0;i<N;i++) arr1[i] = arr[i], pos1[i] = pos[i];
 106         int ind = 0;
 107         for(i=0;i<indiceB;i++){
 108                 if( B[i].first < B[i].second ){
 109                         for(j=B[i].first ; j <= B[i].second;j++)arr[ind] = arr1[j], pos[ind++] = pos1[j];
 110                 }else{
 111                         for(j=B[i].first ; j >= B[i].second;j--)arr[ind] = arr1[j], pos[ind++] = pos1[j];
 112                 }
 113         }
 114 }
 115 int  main(){
 116         int i,j, k;
 117         while(1){
 118                 scanf("%i", &N); if(!N) return 0;
 119                 RES=0;
 120                 for(i=0;i<N;i++) scanf("%i", &arr[i]);
 121                 vector<pair<int,int> > fin;
 122                 for(i=0;i<N;i++) fin.PB(MP(arr[i],i));
 123                 sort(ALL(fin));
 124                 for(i=0;i<fin.size();i++)pos[fin[i].second] = i;
 125                 int sq = (int)sqrt((double)N+0.001);
 126                 int search[1000];
 127                 B[0].first = 0, B[0].second = N-1; indiceB = 1;
 128                 int first = 2;
 129                 for(int ind = 0; ind < N ; ind += sq){
 130                         for(i=0;i<N;i++) if(pos[i] >= ind && pos[i]-ind < sq ) search[pos[i]-ind] = i;
 131                         for(k=0;k<sq&&k+ind<N;k++){
 132                                 change(ind+k,search[k]);
 133                         }
 134                         stable();
 135
 136                         B[0].first = 0, B[0].second = N-1; indiceB = 1;
 137                 }
 138                 for(i=0;i<RES;i++){if(i)printf(" ");printf("%i", res[i]+1);}printf("\n");
 139         }return 0;
 140 }