Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.61 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct ants{
  5. long long pos;
  6. char dir;
  7. long long id;
  8. };
  9.  
  10. bool comp(ants a, ants b){
  11. if(a.pos!=b.pos) return a.pos<b.pos;
  12. return a.dir=='R';
  13. }
  14.  
  15. ants ini[300010],fim[300010];
  16. long long m,t,v,pfi,resp[300010],prox,p,pv,n,pf;
  17. vector <pair<long long,long long>> l,r;
  18.  
  19. long long dist(long long x, long long y){
  20. if(y<x) y+=m;
  21. return y-x;
  22. }
  23.  
  24. long long cnt(long long pl, long long pr, char dir, long long ti){
  25. long long dr,dl,ant=-1,perc=0;
  26. while(true){
  27. if(pl==l.size()) pl=0;
  28. if(pr==r.size()) pr=0;
  29. dr=(r[pr].first+perc)%m;
  30. if(dr<=0) dr+=m;
  31. dl=(l[pl].first-perc)%m;
  32. if(dl<=0) dl+=m;
  33. if(ant>=dist(dr,dl)){
  34. perc++;
  35. dl--;
  36. if(dl<=0) dl+=m;
  37. dr++;
  38. if(dr>m) dr-=m;
  39. }
  40. if(dir=='R'){
  41. if(dist(dr,dl)/2+perc>=ti) return r[pr].second;
  42. pr++;
  43. dir='L';
  44. }
  45. else{
  46. if(dist(dr,dl)/2+perc>=ti) return l[pl].second;
  47. pl++;
  48. dir='R';
  49. }
  50. perc+=dist(dr,dl)/2;
  51. ant=dist(dr,dl)&1;
  52. }
  53. }
  54.  
  55. int main(){
  56. scanf("%lld %lld %lld", &n, &m, &t);
  57. for(long long i=0;i<n;i++){
  58. scanf("%lld", &ini[i].pos);
  59. ini[i].id=i;
  60. scanf(" %c", &ini[i].dir);
  61. fim[i].id=i;
  62. fim[i].dir=ini[i].dir;
  63. if(ini[i].dir=='R') fim[i].pos=(ini[i].pos+t)%m;
  64. else fim[i].pos=(ini[i].pos-t)%m;
  65. if(fim[i].pos<=0) fim[i].pos+=m;
  66. }
  67. sort(ini,ini+n,comp);
  68. sort(fim,fim+n,comp);
  69. while(ini[p].dir=='L' && p<n) p++;
  70. if(p<n) r.push_back({ini[p].pos,p});
  71. for(long long i=p+1;i<n;i++) if(ini[i].dir=='L') l.push_back({ini[i].pos,i});
  72. for(long long i=0;i<p;i++) if(ini[i].dir=='L') l.push_back({ini[i].pos,i});
  73. for(long long i=n-1;i>p;i--) if(ini[i].dir=='R') r.push_back({ini[i].pos,i});
  74. if(r.size()==0 || l.size()==0){
  75. pfi=0;
  76. p=0;
  77. }
  78. else{
  79. pv=cnt(0,0,'R',m)-p;
  80. v=(p+pv*(t/m))%n;
  81. if(ini[v].dir=='L'){
  82. for(prox=0;l[prox].second!=v;prox++);
  83. pv=prox;
  84. if(r[0].first>l[pv].first) pfi=cnt(pv,r.size()-1,'L',t%m);
  85. else{
  86. for(prox=r.size()-1;r[prox].first>l[pv].first;prox--);
  87. pfi=cnt(pv,prox,'L',t%m);
  88. }
  89. }
  90. else{
  91. for(prox=0;r[prox].second!=v;prox++);
  92. pv=prox;
  93. if(r[pv].first>l.back().first) pfi=cnt(0,pv,'R',t%m);
  94. else{
  95. for(prox=0;l[prox].first<r[pv].first;prox++);
  96. pfi=cnt(prox,pv,'R',t%m);
  97. }
  98. }
  99. }
  100. for(pf=0;fim[pf].id!=ini[pfi].id;pf++);
  101. resp[ini[p].id]=fim[pf].pos;
  102. pf++;
  103. for(long long i=p+1;i<n;i++){
  104. if(pf>=n) pf=0;
  105. resp[ini[i].id]=fim[pf].pos;
  106. pf++;
  107. }
  108. for(long long i=0;i<p;i++){
  109. if(pf>=n) pf=0;
  110. resp[ini[i].id]=fim[pf].pos;
  111. pf++;
  112. }
  113. for(long long i=0;i<n-1;i++) printf("%lld ", resp[i]);
  114. printf("%lld\n", resp[n-1]);
  115. return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement