codeforces-scrape

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

1157E.md (1668B)


      1 Source: https://codeforces.com/problemset/problem/1157/E
      2 
      3 E. Minimum Array
      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 You are given two arrays $a$ and $b$, both of length $n$. All elements of both arrays are from $0$ to $n-1$.
     22 
     23 You can reorder elements of the array $b$ (if you want, you may leave the order of elements as it is). After that, let array $c$ be the array of length $n$, the $i$-th element of this array is $c_i = (a_i + b_i) \% n$, where $x \% y$ is $x$ modulo $y$.
     24 
     25 Your task is to reorder elements of the array $b$ to obtain the lexicographically minimum possible array $c$.
     26 
     27 Array $x$ of length $n$ is lexicographically less than array $y$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $x_i \lt y_i$, and for any $j$ ($1 \le j \lt i$) $x_j = y_j$.
     28 
     29 Input
     30 
     31 The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$, $b$ and $c$.
     32 
     33 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \lt n$), where $a_i$ is the $i$-th element of $a$.
     34 
     35 The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \lt n$), where $b_i$ is the $i$-th element of $b$.
     36 
     37 Output
     38 
     39 Print the lexicographically minimum possible array $c$. Recall that your task is to reorder elements of the array $b$ and obtain the lexicographically minimum possible array $c$, where the $i$-th element of $c$ is $c_i = (a_i + b_i) \% n$.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4
     47 0 1 2 1
     48 3 2 1 1
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 1 0 0 2
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 7
     61 2 5 1 5 3 4 3
     62 2 4 3 5 6 5 1
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 0 0 0 1 0 2 4
     69 ```