G2A Many GEOs
SHARE
TWEET

Untitled

a guest Mar 31st, 2020 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top