Berland Music (Codeforces 1622B)
Tags: Greedy, sortings

Berland Music is a music streaming service built specifically to support Berland local artist. Its developers are currently working on a song recommendation module.So imagine Monocarp got recommended $$$n$$$ songs, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th song had its predicted rating equal to $$$p_i$$$, where $$$1 \le p_i \le n$$$ and every integer from $$$1$$$ to $$$n$$$ appears exactly once. In other words, $$$p$$$ is a permutation.After listening to each of them, Monocarp pressed either a like or a dislike button. Let his vote sequence be represented with a string $$$s$$$, such that $$$s_i=0$$$ means that he disliked the $$$i$$$-th song, and $$$s_i=1$$$ means that he liked it.Now the service has to re-evaluate the song ratings in such a way that:  the new ratings $$$q_1, q_2, \dots, q_n$$$ still form a permutation ($$$1 \le q_i \le n$$$; each integer from $$$1$$$ to $$$n$$$ appears exactly once);  every song that Monocarp liked should have a greater rating than every song that Monocarp disliked (formally, for all $$$i, j$$$ such that $$$s_i=1$$$ and $$$s_j=0$$$, $$$q_i>q_j$$$ should hold). Among all valid permutations $$$q$$$ find the one that has the smallest value of $$$\sum\limits_{i=1}^n |p_i-q_i|$$$, where $$$|x|$$$ is an absolute value of $$$x$$$.Print the permutation $$$q_1, q_2, \dots, q_n$$$. If there are multiple answers, you can print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of songs.The second line of each testcase contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation of the predicted ratings.The third line contains a single string $$$s$$$, consisting of $$$n$$$ characters. Each character is either a $$$0$$$ or a $$$1$$$. $$$0$$$ means that Monocarp disliked the song, and $$$1$$$ means that he liked it.The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print a permutation $$$q$$$ — the re-evaluated ratings of the songs. If there are multiple answers such that $$$\sum\limits_{i=1}^n |p_i-q_i|$$$ is minimum possible, you can print any of them.

Note: In the first testcase, there exists only one permutation $$$q$$$ such that each liked song is rating higher than each disliked song: song $$$1$$$ gets rating $$$2$$$ and song $$$2$$$ gets rating $$$1$$$. $$$\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$$$.In the second testcase, Monocarp liked all songs, so all permutations could work. The permutation with the minimum sum of absolute differences is the permutation equal to $$$p$$$. Its cost is $$$0$$$.

Sample Inputs:
3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001

Sample Outputs:
2 1
3 1 2
1 6 5 8 3 2 4 7

Solution (Python):
def solve(n: int, l: list, s: str):
    ans = [-1] * n
    boarder = s.count('0')
    l1 = []
    l0 = []
    for i in range(n):
        if s[i] == '1' and l[i] > boarder:
            ans[i] = l[i]
            l[i] = -1
        elif s[i] == '0' and l[i] <= boarder:
            ans[i] = l[i]
            l[i] = -1
        elif l[i] > boarder:
            l1.append(l[i])
        elif l[i] <= boarder:
            l0.append(l[i])
    for i in range(n):
        if ans[i] == -1:
            if s[i] == '1':
                ans[i] = l1[-1]
                l1.pop()
            else:
                ans[i] = l0[-1]
                l0.pop()
    print(*ans)
for i in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    s = input()
    solve(n, l, s)

Solution (Python):
def solve(n, a, s):
    ar = [0] * n
    if s == ['1'] * n or s == ['0'] * n:
        a = list(map(str, a))
        return ' '.join(a)
    for i in range(n):
        ar[a[i] - 1] = i
    c = 1
    ans = [0] * n
    for i in range(n):
        if s[ar[i]] == '0':
            ans[ar[i]] = c
            c += 1
    for i in range(n):
        if s[ar[i]] == '1':
            ans[ar[i]] = c
            c += 1
    ans = list(map(str, ans))
    return ' '.join(ans)
for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s = list(input())
    print(solve(n, a, s))

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    p = list(map(int, inp().split()))
    pi = [None] * (n + 1)
    for i in range(n):
        pi[p[i]] = i
    s = inp()
    ans = [None] * n
    c = [0, 0]
    for i in range(1, n + 1):
        x = pi[i]
        y = int(s[x])
        ans[x] = c[y]
        c[y] += 1
    o = [1, 1 + c[0]]
    for i in range(1, n + 1):
        x = pi[i]
        y = int(s[x])
        ans[x] += o[y]
    print(' '.join(map(str, ans)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()