codeforces-scrape

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

1990B.md (1675B)


      1 Source: https://codeforces.com/problemset/problem/1990/B
      2 
      3 B. Array Craft
      4 
      5 time limit per test
      6 
      7 1 second
      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 For an array $b$ of size $m$, we define:
     22 
     23 * the maximum prefix position of $b$ is the smallest index $i$ that satisfies $b_1+\ldots+b_i=\max_{j=1}^{m}(b_1+\ldots+b_j)$;
     24 * the maximum suffix position of $b$ is the largest index $i$ that satisfies $b_i+\ldots+b_m=\max_{j=1}^{m}(b_j+\ldots+b_m)$.
     25 
     26 You are given three integers $n$, $x$, and $y$ ($x \gt y$). Construct an array $a$ of size $n$ satisfying:
     27 
     28 * $a_i$ is either $1$ or $-1$ for all $1 \le i \le n$;
     29 * the maximum prefix position of $a$ is $x$;
     30 * the maximum suffix position of $a$ is $y$.
     31 
     32 If there are multiple arrays that meet the conditions, print any. It can be proven that such an array always exists under the given conditions.
     33 
     34 Input
     35 
     36 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     37 
     38 For each test case:
     39 
     40 * The only line contains three integers $n$, $x$, and $y$ ($2 \leq n \leq 10^5, 1 \le y \lt x \le n)$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, output $n$ space-separated integers $a_1, a_2, \ldots, a_n$ in a new line.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 3
     54 
     55 2 2 1
     56 
     57 4 4 3
     58 
     59 6 5 1
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 1 1
     66 1 -1 1 1
     67 1 1 -1 1 1 -1
     68 ```
     69 
     70 Note
     71 
     72 In the second test case,
     73 
     74 * $i=x=4$ is the smallest index that satisfies $a_1+\ldots +a_i=\max_{j=1}^{n}(a_1+\ldots+a_j)=2$;
     75 * $i=y=3$ is the greatest index that satisfies $a_i+\ldots +a_n=\max_{j=1}^{n}(a_j+\ldots+a_n)=2$.
     76 
     77 Thus, the array $a=[1,-1,1,1]$ is considered correct.