codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1622B.md (2891B)


      1 Source: https://codeforces.com/problemset/problem/1622/B
      2 
      3 B. Berland Music
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Berland Music is a music streaming service built specifically to support Berland local artist. Its developers are currently working on a song recommendation module.
     22 
     23 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.
     24 
     25 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.
     26 
     27 Now the service has to re-evaluate the song ratings in such a way that:
     28 
     29 * 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);
     30 * 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 \gt q_j$ should hold).
     31 
     32 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$.
     33 
     34 Print the permutation $q_1, q_2, \dots, q_n$. If there are multiple answers, you can print any of them.
     35 
     36 Input
     37 
     38 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     39 
     40 The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of songs.
     41 
     42 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.
     43 
     44 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.
     45 
     46 The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.
     47 
     48 Output
     49 
     50 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.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 3
     58 2
     59 1 2
     60 10
     61 3
     62 3 1 2
     63 111
     64 8
     65 2 3 1 8 5 4 7 6
     66 01110001
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2 1
     73 3 1 2
     74 1 6 5 8 3 2 4 7
     75 ```
     76 
     77 Note
     78 
     79 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$.
     80 
     81 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$.