Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Жақшалар тізбегі — ( және ) таңбаларынан құралған жол. $s_{1,2,\ldots,m}$ жақшалар тізбегі келесі шарттардың бірін қанағаттандырса, дұрыс деп аталады:

  • $s$ бос.
  • $s_1 = $ (, $s_m = $ ), және $s_{2,3,\ldots,m-1}$ дұрыс.
  • $s_{1,2,\ldots,k}$ дұрыс және $s_{k+1,k+2,\ldots,m}$ дұрыс болатындай $k$ ($1 \le k < m$) орны табылады.

$s_{1,2,\ldots,m}$ жақшалар тізбегіндегі екі $i, j$ ($1 \le i < j \le m$) орны тек $s_{i,i+1,\ldots,j}$ мен $s_{i+1,i+2,\ldots,j-1}$ екеуі де дұрыс болғанда ғана жұптасқан деп аталады.

Ұзындығы $n$ болатын $a_1, a_2, \ldots, a_n$ бүтін сандар тізбегі берілген, мұндағы $n$ жұп сан екеніне кепілдік беріледі. Біз дұрыс $b_1, b_2, \ldots, b_n$ жақшалар тізбегі арқылы $\forall 1 \le i \le n, c_i = a_{p_i}$ болатындай жаңа $c_1, c_2, \ldots, c_n$ бүтін сандар тізбегін құрамыз, мұндағы $p_i$ — $b_{1,2,\ldots,n}$ тізбегіндегі $i$ орнымен жұптасқан орын.

$c_{1,2,\ldots,n}$ тізбегінің лексикографиялық реті ең кіші болатындай дұрыс $b_{1,2,\ldots,n}$ жақшалар тізбегін табыңыз. Егер шешімдер бірнешеу болса, олардың кез келгенін шығарыңыз.

Кіріс деректері

Бірінші жолда тест жағдайларының санын білдіретін бүтін сан $T$ ($1 \le T \le 2.5 \times 10^5$) берілген.

Әрбір тест жағдайы үшін:

Бірінші жолда $a$ тізбегінің ұзындығын білдіретін бүтін сан $n$ ($1 \le n \le 5 \times 10^5$) берілген, және $n$ жұп сан екеніне кепілдік беріледі.

Екінші жолда $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) мәндерін білдіретін бос орын арқылы бөлінген $n$ бүтін сан берілген.

Барлық тест жағдайлары бойынша $n$ қосындысы $5 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректері

Әрбір тест жағдайы үшін $b_{1,2,\ldots,n}$ тізбегін білдіретін ұзындығы $n$ болатын жолды шығарыңыз.

Мысалдар

Кіріс деректері 1

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

Шығыс деректері 1

((()))
()()
(())
()
((()))()

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.