871 . 題目測試

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Gu2
女兒走在書店，指著一本書大喊「爸爸！這個名字我好像有看過！」我看到他指的名字“八奈見杏菜”不禁笑了笑，指著配偶欄說道「這是媽媽的名字，以後要記清楚喔」

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

42.9% (6/14)

Tags

ntucpc-speedrun1

Description

NSSPC 2024 即將來臨，裁判們必須盡快把題目準備好。裁判團隊有 N 個人，他們打算要出總共 N 道題目，這 N 道題目從 1 到 N 編號，題目 i 的出題者是裁判 i。

為了確保題目品質，每道題目都要由出題者之外的另一名裁判負責測試，確定題目沒有問題。仔細地說，每一個裁判都要負責測試恰好一道題目，且每道題目都要恰有一個裁判負責測試，這個負責測試的裁判不能和出題者是同一個人。已經有一些裁判先選定了他們要負責測試的題目了，因為出題期限將近，所以你必須盡快為剩下的裁判分配他們要負責測試的題目。

Input Format

第一行包含一個整數 T，代表接下來測試資料的組數。

每一筆測試資料的第一行包含一個整數 N，代表裁判的人數，同時也是要出的題目的數量。

第二行包含 N 個整數 a1,a2,…,aN。對於 1≤i≤N，如果 ai≠−1，代表裁判 i 已經選定了要負責測試題目 ai；如果 ai=−1，代表裁判 i 還沒選擇要負責測試哪道題目。

  • 1≤T
  • 2≤N≤105
  • T 筆測試資料中的 N 總和 ≤105
  • 1≤ai≤N 或 ai=−1
  • 保證有辦法為所有 ai=−1 的裁判指定負責測試的題目，滿足所有要求

Output Format

對於每筆測試資料，輸出一行，包含 N 個整數 b1,b2,…,bN，其中 1≤bi≤N，代表你分配之後，裁判 i 負責測試題目 bi。如果本來一個裁判已經選定要測試哪一題，你必須保留他本來選定的題目。正式地說，你輸出的答案必須滿足以下所有條件：

  • 1≤bi≤N
  • bi≠i
  • 如果 ai≠−1，那麼 bi=ai
  • 對於 1≤j≤N，恰有一個 i 滿足 bi=j

Sample Input 1

5
5
-1 -1 -1 -1 -1
5
3 4 2 5 1
3
3 -1 -1
3
-1 -1 1
10
3 -1 -1 5 2 -1 1 6 -1 4

Sample Output 1

2 3 4 5 1
3 4 2 5 1
3 1 2
2 3 1
3 8 10 5 2 9 1 6 7 4

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
Submit
Back to Top