Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- struct ants{
- long long pos;
- char dir;
- long long id;
- };
- bool comp(ants a, ants b){
- if(a.pos!=b.pos) return a.pos<b.pos;
- return a.dir=='R';
- }
- ants ini[300010],fim[300010];
- long long m,t,v,pfi,resp[300010],prox,p,pv,n,pf;
- vector <pair<long long,long long>> l,r;
- long long dist(long long x, long long y){
- if(y<x) y+=m;
- return y-x;
- }
- long long cnt(long long pl, long long pr, char dir, long long ti){
- long long dr,dl,ant=-1,perc=0;
- while(true){
- if(pl==l.size()) pl=0;
- if(pr==r.size()) pr=0;
- dr=(r[pr].first+perc)%m;
- if(dr<=0) dr+=m;
- dl=(l[pl].first-perc)%m;
- if(dl<=0) dl+=m;
- if(ant>=dist(dr,dl)){
- perc++;
- dl--;
- if(dl<=0) dl+=m;
- dr++;
- if(dr>m) dr-=m;
- }
- if(dir=='R'){
- if(dist(dr,dl)/2+perc>=ti) return r[pr].second;
- pr++;
- dir='L';
- }
- else{
- if(dist(dr,dl)/2+perc>=ti) return l[pl].second;
- pl++;
- dir='R';
- }
- perc+=dist(dr,dl)/2;
- ant=dist(dr,dl)&1;
- }
- }
- int main(){
- scanf("%lld %lld %lld", &n, &m, &t);
- for(long long i=0;i<n;i++){
- scanf("%lld", &ini[i].pos);
- ini[i].id=i;
- scanf(" %c", &ini[i].dir);
- fim[i].id=i;
- fim[i].dir=ini[i].dir;
- if(ini[i].dir=='R') fim[i].pos=(ini[i].pos+t)%m;
- else fim[i].pos=(ini[i].pos-t)%m;
- if(fim[i].pos<=0) fim[i].pos+=m;
- }
- sort(ini,ini+n,comp);
- sort(fim,fim+n,comp);
- while(ini[p].dir=='L' && p<n) p++;
- if(p<n) r.push_back({ini[p].pos,p});
- for(long long i=p+1;i<n;i++) if(ini[i].dir=='L') l.push_back({ini[i].pos,i});
- for(long long i=0;i<p;i++) if(ini[i].dir=='L') l.push_back({ini[i].pos,i});
- for(long long i=n-1;i>p;i--) if(ini[i].dir=='R') r.push_back({ini[i].pos,i});
- if(r.size()==0 || l.size()==0){
- pfi=0;
- p=0;
- }
- else{
- pv=cnt(0,0,'R',m)-p;
- v=(p+pv*(t/m))%n;
- if(ini[v].dir=='L'){
- for(prox=0;l[prox].second!=v;prox++);
- pv=prox;
- if(r[0].first>l[pv].first) pfi=cnt(pv,r.size()-1,'L',t%m);
- else{
- for(prox=r.size()-1;r[prox].first>l[pv].first;prox--);
- pfi=cnt(pv,prox,'L',t%m);
- }
- }
- else{
- for(prox=0;r[prox].second!=v;prox++);
- pv=prox;
- if(r[pv].first>l.back().first) pfi=cnt(0,pv,'R',t%m);
- else{
- for(prox=0;l[prox].first<r[pv].first;prox++);
- pfi=cnt(prox,pv,'R',t%m);
- }
- }
- }
- for(pf=0;fim[pf].id!=ini[pfi].id;pf++);
- resp[ini[p].id]=fim[pf].pos;
- pf++;
- for(long long i=p+1;i<n;i++){
- if(pf>=n) pf=0;
- resp[ini[i].id]=fim[pf].pos;
- pf++;
- }
- for(long long i=0;i<p;i++){
- if(pf>=n) pf=0;
- resp[ini[i].id]=fim[pf].pos;
- pf++;
- }
- for(long long i=0;i<n-1;i++) printf("%lld ", resp[i]);
- printf("%lld\n", resp[n-1]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement