D - Message from Aliens (ATCODER)

PROBLEM LINK :   https://atcoder.jp/contests/zone2021/tasks/zone2021_d

Problem Statement

You are given a ciphertext $S$. It can be decrypted by the following procedure:

• Let $T$ be an empty string.
• For each $i=1,2,\dots ,|S|$ in this order, do the following: ($|S|$ denotes the length of $S$)
  • if the $i$-th character of $S$ is R, reverse $T$;
  • if the $i$-th character of $S$ is not R, add that character to the end of $T$.
• After the operation above, if there are two consecutive same characters in $T$, remove those two characters. Repeat this operation as long as it can be done. (We can prove that the final string obtained does not depend on the order the characters are removed.)

Print the string $T$ obtained by this procedure.

Constraints

• $S$ consists of lowercase English letters and R.
• $1\le |S|\le 5\times {10}^5$

---

SOLUTION BY DEQUE:

// Problem: D - Message from Aliens

// Contest: AtCoder - ZONe Energy Programming Contest

// URL: https://atcoder.jp/contests/zone2021/tasks/zone2021_d

// Memory Limit: 1024 MB

// Time Limit: 2000 ms

//

// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define pII pair<int,int>

#define mem(a,b) memset(a,b,sizeof(a))

#define rep(i, a, b) for (int i = a; i < b; i++)

#define do(i, a, b) for (int i= (a); i <= (b); i++)

#define com(s) (s).begin(),(s).end()

#define F first

#define S second

#define pb push_back

#define s(x) (int)(x).size()

#define CASES int tc;cin>>tc;while(tc--)

#define READ_INP freopen("inp.txt", "r", stdin)

#define UNIQUE(X) (X).erase(unique(S(X)),(X).end())

#define IOs ios_base::sync_with_stdio(false);cin.tie(NULL);

#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())

#define DISPV(v) { for(auto u: v) cout << u << " "; cout << endl; }

#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))

#define endl '\n'

const int inf = 1e18; const int M = 1e9 + 7; const int MAXN = 1e7 + 1;

const double pi = acos(-1.0);

//DEBUGGING-TOOL

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}

template<typename T, typename... Args>

void err(istream_iterator<string> it, T a, Args... args) {

cerr <<*it << " = " << a << endl;

err(++it, args...);

}

//FUNC

int gcd(int a, int b) {return b == 0?a:gcd(b, a % b);}

int modMul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}

int modPow(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}

int calculateNcR(int n, int r){ if(n<r)return 0; int p=1,k=1;if(n-r<r)r=n-r;if(r!=0){while(r){p*=n;k*=r;int m=gcd(p, k);p/=m;k/=m;n--;r--;}return p;}}

//CODE

int32_t main() {

IOs;

// CASES {

int n,m,l,r,d,b,k,u,p,a,q,x,y,z,mn,mx,rem,ans,res=0,c=0;

string s; cin >> s;

deque<char>Deq;

int ok = 0;

for (char I: s){

if(I == 'R') ok ^= 1;

else if(ok == 1) Deq.push_front(I);

else Deq.push_back(I);

}

if(ok == 1) reverse(Deq.begin(), Deq.end());

string Ano;

for (char d: Deq){

if(s(Deq) == 0) Ano.push_back(d);

else{

if(Ano.back() == d) Ano.pop_back();

else Ano.push_back(d);

}

}

cout << Ano << '\n';

// }

}