1
0

happybirthday.cpp 2.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include "happybirthday_lib_c.h"
  4. #include "happybirthday_lib_c.cpp"
  5. const int BLOCKSIZE = 1000;
  6. const int MAXL = 500000+10;
  7. const int MAXB = 2*MAXL/BLOCKSIZE+100;
  8. int frcount[MAXL];
  9. int freelist[MAXB];
  10. int freepos;
  11. int newnode(){
  12. return freelist[freepos++];
  13. }
  14. void delnode(int t){
  15. freelist[--freepos]=t;
  16. }
  17. int next[MAXB];
  18. int data[MAXB][BLOCKSIZE];
  19. int bcount[MAXB];
  20. int account;
  21. void find(int &p, int &b){
  22. for(b=0; b!=-1 && p>bcount[b]; b=next[b])
  23. p -= bcount[b];
  24. }
  25. void fillblock(int b,int str[],int n,int e){
  26. next[b]=e;
  27. bcount[b]=n;
  28. memcpy(data[b], str, n*sizeof(int));
  29. }
  30. void splite(int b,int p){
  31. if(b==-1 || bcount[b]==p)return;
  32. int t=newnode();
  33. fillblock(t, data[b]+p, bcount[b]-p, next[b]);
  34. next[b]=t;
  35. bcount[b]=p;
  36. }
  37. void maintainlist(int b){
  38. int t;
  39. while(b!=-1 && (t=next[b])!=-1 && bcount[b] + bcount[t] < BLOCKSIZE){
  40. memcpy(data[b]+bcount[b], data[t], bcount[t]*sizeof(int));
  41. bcount[b]+=bcount[t];
  42. next[b]=next[t];
  43. delnode(t);
  44. }
  45. }
  46. int rank(int key){
  47. int b,rank=0,i;
  48. for(b=0; b!=-1 && next[b]!=-1 && frcount[data[next[b]][0]]<key; b=next[b])
  49. rank += bcount[b];
  50. for(i=0; i<bcount[b]; ++i)if(frcount[data[b][i]]>=key)break;
  51. rank += i-1;
  52. return rank;
  53. }
  54. int insert(int people){
  55. int b, p = rank(frcount[people])+1;
  56. find(p, b);
  57. if(bcount[b] == BLOCKSIZE){
  58. splite(b, p);
  59. if(p==BLOCKSIZE){
  60. p=0;
  61. b=next[b];
  62. if(bcount[b]==BLOCKSIZE)splite(b, p);
  63. }
  64. }
  65. for(int i=bcount[b]; i>p; --i)data[b][i]=data[b][i-1];
  66. data[b][p]=people;
  67. ++bcount[b];
  68. ++account;
  69. }
  70. int remove(int p){
  71. int b;
  72. find(p, b);
  73. if(p == bcount[b]){
  74. b=next[b];
  75. p=0;
  76. }
  77. for(int i=p; i<bcount[b]; ++i)data[b][i]=data[b][i+1];
  78. --bcount[b];
  79. --account;
  80. maintainlist(b);
  81. }
  82. int select(int rank){
  83. int b;
  84. find(rank, b);
  85. if(rank==bcount[b]){b=next[b]; rank=0;}
  86. return data[b][rank];
  87. }
  88. void initlist(){
  89. for(int i=1; i<MAXB; ++i)freelist[i]=i;
  90. freepos=1;
  91. next[0]=-1;
  92. account=bcount[0]=0;
  93. }
  94. int main(){
  95. init();
  96. initlist();
  97. long n=0,c,lukynumber,r,order;
  98. bool isboy;
  99. int people;
  100. while(getpresent(c,lukynumber,isboy)){
  101. ++n;
  102. frcount[n]=c;
  103. insert(n);
  104. r=rank(c)+1;
  105. r+=lukynumber*(isboy?1:-1);
  106. if(r<0||r>=account)tell(-1);
  107. else{
  108. people=select(r);
  109. tell(people);
  110. remove(r);
  111. if(--frcount[people])insert(people);
  112. }
  113. }
  114. return 0;
  115. }