codeforces-scrape

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

1530D.md (2439B)


      1 Source: https://codeforces.com/problemset/problem/1530/D
      2 
      3 D. Secret Santa
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Every December, VK traditionally holds an event for its employees named "Secret Santa". Here's how it happens.
     22 
     23 $n$ employees numbered from $1$ to $n$ take part in the event. Each employee $i$ is assigned a different employee $b_i$, to which employee $i$ has to make a new year gift. Each employee is assigned to exactly one other employee, and nobody is assigned to themselves (but two employees may be assigned to each other). Formally, all $b_i$ must be distinct integers between $1$ and $n$, and for any $i$, $b_i \ne i$ must hold.
     24 
     25 The assignment is usually generated randomly. This year, as an experiment, all event participants have been asked who they wish to make a gift to. Each employee $i$ has said that they wish to make a gift to employee $a_i$.
     26 
     27 Find a valid assignment $b$ that maximizes the number of fulfilled wishes of the employees.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.
     32 
     33 Each test case consists of two lines. The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of participants of the event.
     34 
     35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$; $a_i \ne i$) — wishes of the employees in order from $1$ to $n$.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print two lines.
     42 
     43 In the first line, print a single integer $k$ ($0 \le k \le n$) — the number of fulfilled wishes in your assignment.
     44 
     45 In the second line, print $n$ distinct integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$; $b_i \ne i$) — the numbers of employees assigned to employees $1, 2, \ldots, n$.
     46 
     47 $k$ must be equal to the number of values of $i$ such that $a_i = b_i$, and must be as large as possible. If there are multiple answers, print any.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 2
     55 3
     56 2 1 2
     57 7
     58 6 4 6 2 4 5 6
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2
     65 3 1 2
     66 4
     67 6 4 7 2 3 5 1
     68 ```
     69 
     70 Note
     71 
     72 In the first test case, two valid assignments exist: $[3, 1, 2]$ and $[2, 3, 1]$. The former assignment fulfills two wishes, while the latter assignment fulfills only one. Therefore, $k = 2$, and the only correct answer is $[3, 1, 2]$.