sort.cpp 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  4. #include<time.h>
  5. const int oo = 2000000000;
  6. const int MAXN = 100000+10;
  7. const int BLOCKSIZE = 200;
  8. const int MAXBLOCK = MAXN/BLOCKSIZE*2+100;
  9. void swap(int &a,int &b){a^=b;b^=a;a^=b;}
  10. int min(int a,int b){return a<b?a:b;}
  11. int freelist[MAXBLOCK];
  12. int freepos;
  13. int newnode(){
  14. return freelist[freepos++];
  15. }
  16. void delnode(int t){
  17. freelist[--freepos]=t;
  18. }
  19. int data[MAXBLOCK][BLOCKSIZE];
  20. int minimum[MAXBLOCK];
  21. int count[MAXBLOCK];
  22. int next[MAXBLOCK];
  23. bool reversed[MAXBLOCK];
  24. void find(int &p,int &b){
  25. for(b=0; p>count[b]; b=next[b])p-=count[b];
  26. }
  27. void reverseblock(int b){
  28. if(b==-1 || !reversed[b])return;
  29. reversed[b]=false;
  30. for(int l=0,r=count[b]-1; l<r; ++l,--r)swap(data[b][l],data[b][r]);
  31. }
  32. void maintainblock(int b){
  33. minimum[b]=oo;
  34. for(int i=count[b]-1; i>=0; --i)
  35. minimum[b]=min(minimum[b], data[b][i]);
  36. }
  37. void fillblock(int b, int str[], int n, int e){
  38. next[b]=e;
  39. count[b]=n;
  40. memcpy(data[b], str, n*sizeof(int));
  41. maintainblock(b);
  42. }
  43. void splite(int b,int p){
  44. if(b==-1 || count[b]==p)return;
  45. reverseblock(b);
  46. int t=newnode();
  47. fillblock(t, data[b]+p, count[b]-p, next[b]);
  48. count[b]=p;
  49. next[b]=t;
  50. maintainblock(b);
  51. }
  52. void maintainlist(int b){
  53. for(bool x=false; b!=-1; b=next[b],x=false){
  54. for(int t=next[b]; t!=-1 && count[b] + count[t] <= BLOCKSIZE; t=next[b]){
  55. x=true;
  56. next[b]=next[t];
  57. reverseblock(b);
  58. reverseblock(t);
  59. memcpy(data[b]+count[b], data[t], count[t]*sizeof(int));
  60. count[b]+=count[t];
  61. delnode(t);
  62. }
  63. if(x)maintainblock(b);
  64. }
  65. }
  66. void insert(int p,int n,int str[]){
  67. int b,i,t;
  68. find(p,b);
  69. splite(b,p);
  70. for(i=0; i+BLOCKSIZE <= n; i+=BLOCKSIZE){
  71. t=newnode();
  72. fillblock(t, str+i, BLOCKSIZE, next[b]);
  73. next[b]=t;
  74. b=t;
  75. }
  76. if(n-i){
  77. t=newnode();
  78. fillblock(t, str+i, n-i, next[b]);
  79. next[b]=t;
  80. }
  81. maintainlist(b);
  82. }
  83. void erase(int p,int n){
  84. int b,e;
  85. find(p,b);
  86. splite(b,p);
  87. for(e=next[b]; n>count[e]; e=next[e])n-=count[e];
  88. splite(e,n);
  89. e=next[e];
  90. for(int t=next[b]; t!=e; t=next[b]){
  91. next[b]=next[t];
  92. delnode(t);
  93. }
  94. maintainlist(b);
  95. }
  96. int list[MAXBLOCK];
  97. void reverse(int p,int n){
  98. int b,e,i,t;
  99. find(p,b);
  100. splite(b,p);
  101. for(e=next[b]; n>count[e]; e=next[e])n-=count[e];
  102. splite(e,n);
  103. e=next[e];
  104. for(t=next[b],i=0; t!=e; ++i,t=next[t])list[i]=t;
  105. next[b]=list[--i];
  106. for(; i>=0; --i){
  107. next[list[i]] = i ? list[i-1] : e;
  108. reversed[list[i]] = ! reversed[list[i]];
  109. }
  110. maintainlist(b);
  111. }
  112. int findnum(int r){
  113. int n=0,b,i,delta;
  114. for(b=0; b!=-1 && minimum[b]!=r; b=next[b])n+=count[b];
  115. if(reversed[b]){i=count[b]-1;delta=-1;}
  116. else {i=0;delta=1;}
  117. for(; ; i+=delta,++n)if(data[b][i]==r)break;
  118. return n+1;
  119. }
  120. void init(){
  121. for(int i=1; i<MAXBLOCK; ++i)freelist[i]=i;
  122. freepos=1;
  123. next[0]=-1;
  124. count[0]=0;
  125. }
  126. int tstr[MAXN],tstr2[MAXN];
  127. int n;
  128. int cmp(const void *a,const void *b){
  129. int xa=*((int*)a);
  130. int xb=*((int*)b);
  131. if(tstr[xa]!=tstr[xb])return tstr[xa] - tstr[xb];
  132. return xa - xb;
  133. }
  134. void solve(){
  135. int i,p;
  136. for(i=0; i<n; ++i)scanf("%d",tstr+i);
  137. for(i=0; i<n; ++i)tstr2[i]=i;
  138. qsort(tstr2, n, sizeof(int), cmp);
  139. for(i=0; i<n; ++i)tstr[tstr2[i]]=i;
  140. insert(0, n, tstr);
  141. for(i=0; i<n; ++i){
  142. p=findnum(i);
  143. if(i)printf(" ");
  144. printf("%d",i+p);
  145. if(p>1)reverse(0,p);
  146. erase(0,1);
  147. }
  148. printf("\n");
  149. }
  150. int main(){
  151. while(scanf("%d",&n)==1 && n){
  152. init();
  153. solve();
  154. }
  155. fprintf(stderr, "%.2lf\n", clock()/(double)CLOCKS_PER_SEC);
  156. }