Robot Collisions (Codeforces 1525C)
Tags: Greedy, sortings

There are $$$n$$$ robots driving along an OX axis. There are also two walls: one is at coordinate $$$0$$$ and one is at coordinate $$$m$$$.The $$$i$$$-th robot starts at an integer coordinate $$$x_i~(0 < x_i < m)$$$ and moves either left (towards the $$$0$$$) or right with the speed of $$$1$$$ unit per second. No two robots start at the same coordinate.Whenever a robot reaches a wall, it turns around instantly and continues his ride in the opposite direction with the same speed.Whenever several robots meet at the same integer coordinate, they collide and explode into dust. Once a robot has exploded, it doesn't collide with any other robot. Note that if several robots meet at a non-integer coordinate, nothing happens.For each robot find out if it ever explodes and print the time of explosion if it happens and $$$-1$$$ otherwise.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.Then the descriptions of $$$t$$$ testcases follow.The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^8$$$) — the number of robots and the coordinate of the right wall.The second line of each testcase contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 < x_i < m$$$) — the starting coordinates of the robots.The third line of each testcase contains $$$n$$$ space-separated characters 'L' or 'R' — the starting directions of the robots ('L' stands for left and 'R' stands for right).All coordinates $$$x_i$$$ in the testcase are distinct.The sum of $$$n$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each testcase print $$$n$$$ integers — for the $$$i$$$-th robot output the time it explodes at if it does and $$$-1$$$ otherwise.

Note: Here is the picture for the seconds $$$0, 1, 2$$$ and $$$3$$$ of the first testcase:   Notice that robots $$$2$$$ and $$$3$$$ don't collide because they meet at the same point $$$2.5$$$, which is not integer.After second $$$3$$$ robot $$$6$$$ just drive infinitely because there's no robot to collide with.

Sample Inputs:
5
7 12
1 2 3 4 9 10 11
R R L L R R R
2 10
1 6
R R
2 10
1 3
L L
1 10
5
R
7 8
6 1 7 2 3 5 4
R L R L L L L

Sample Outputs:
1 1 1 1 2 -1 2 
-1 -1 
2 2 
-1 
-1 2 7 3 2 7 3

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def read():
    t = int(input())
    for _ in range(t):
        (n, m) = map(int, input().split())
        x = list(map(int, input().split()))
        d = list(input().split())
        solve(n, m, x, d)

def solve(n, m, xs, d):
    ix = [i for i in range(n)]
    ix.sort(key=lambda i: xs[i])
    st_odd = []
    st_even = []
    ans = [-1] * n
    for i in range(n):
        ind = ix[i]
        pos = xs[ind]
        if pos % 2 == 0:
            st = st_even
        else:
            st = st_odd
        if d[ind] == b'L':
            if len(st) > 0:
                pre_ind = st[-1]
                st.pop()
                if d[pre_ind] == b'L':
                    pre_pos = -xs[pre_ind]
                else:
                    pre_pos = xs[pre_ind]
                time = (pos - pre_pos) // 2
                ans[ind] = time
                ans[pre_ind] = time
            else:
                st.append(ind)
        else:
            st.append(ind)
    for st in (st_odd, st_even):
        while len(st) > 1:
            r = st.pop()
            l = st.pop()
            l_pos = xs[l]
            if d[l] == b'L':
                l_pos = -l_pos
            r_pos = 2 * m - xs[r]
            time = (r_pos - l_pos) // 2
            ans[r] = time
            ans[l] = time
    sys.stdout.write(' '.join(map(str, ans)))
    sys.stdout.write('\n')
if __name__ == '__main__':
    read()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from operator import itemgetter

def solve(n, m, x, s):
    arr = sorted([(i, x[i], s[i]) for i in range(n)], key=itemgetter(1))
    stacks = [[], []]
    ans = [-1] * n
    for (i, xi, si) in arr:
        stk = stacks[xi % 2]
        if not stk:
            stk.append((i, xi, si))
        else:
            (oi, ox, os) = stk[-1]
            if os == 'R' and si == 'L':
                ans[i] = ans[oi] = (xi - ox) // 2
                stk.pop()
            elif os == 'L' and si == 'L':
                ans[i] = ans[oi] = (xi + ox) // 2
                stk.pop()
            else:
                stk.append((i, xi, si))
    for stk in stacks:
        stk.reverse()
        l = len(stk)
        for i in range(0, l, 2):
            if i >= l - 2:
                break
            (ii, xi, _) = stk[i]
            (oi, ox, _) = stk[i + 1]
            ans[ii] = ans[oi] = (2 * m - ox - xi) // 2
        if i == l - 2:
            (ii, xi, si) = stk[i]
            (oi, ox, os) = stk[i + 1]
            if si == 'R' and os == 'R':
                ans[ii] = ans[oi] = (2 * m - ox - xi) // 2
            elif si == 'R' and os == 'L':
                ans[ii] = ans[oi] = (2 * m - xi + ox) // 2
    print(*ans)

def main():
    for t in range(int(input())):
        (n, m) = map(int, input().split())
        x = list(map(int, input().split()))
        s = input().split()
        solve(n, m, x, s)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, stdout
import math, bisect, heapq
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
    print(' '.join(list(map(str, a))))

def solve():
    (n, m) = L()
    a = L()
    b = C()
    c = [(a[i], b[i], i) for i in range(n)]
    c.sort()
    (odd, even) = ([], [])
    ans = [-1] * n
    for i in range(n):
        (x, y, z) = c[i]
        if y == 'R':
            if x % 2:
                odd += [(z, x)]
            else:
                even += [(z, x)]
        elif x % 2:
            if odd:
                temp = odd.pop()
                p = (x - temp[1]) // 2
                ans[z] = ans[temp[0]] = p
            else:
                odd += [(z, -x)]
        elif even:
            temp = even.pop()
            p = (x - temp[1]) // 2
            ans[z] = ans[temp[0]] = p
        else:
            even += [(z, -x)]
    while len(even) >= 2:
        p = even.pop()
        q = even.pop()
        ans[p[0]] = ans[q[0]] = (p[1] - q[1]) // 2 + (m - p[1])
    even = odd
    while len(even) >= 2:
        p = even.pop()
        q = even.pop()
        ans[p[0]] = ans[q[0]] = (p[1] - q[1]) // 2 + (m - p[1])
    pr(ans)
for _ in range(I()):
    solve()