Superpozicija
레이팅 미적용의견: 0
1 sekun\(da / 512\) M\(iB / 110\) points
Wor\(ld-re\)nowned physicist Juraj has recently discovered a new kind of elementary particle – a parenthesision.
A parenthesision can have either an open ’(’ or ’)’ closed configuration. Using his homemade particle
accelerator, Juraj has created \(t\) sequences of superpositions of \(n\) parenthesisions. In each of the \(t\) sequences
there are \(n\) parenthesisions in a superposition between two different positions positions and (not necessarily
different) configurations. If the sequence is observed, the wave function of parenthesisions collapses and
each of them ends up in one of it’s possible positions and configurations. Juraj wants to know if it is
possible that the parenthesisions collapse into a valid sequence of parenthesis?
Juraj M. PhD knows that the quantum physics of these revolutionary and completely scientifically founded
particles are way over the head of an average COCI contestant, so he provided a formal task statement:
You are given \(t\) sequences of 2\(n\) open and closed parenthesis. Each of the parenthesis is a member of
exactly one pair of parenthesis. Two parenthesis within a pair can be different, both open, or both closed.
Juraj wants to know if it is possible to chose a single parenthesis from each of the pairs such that the
chosen parentheses form a valid sequence of parentheses. Furthermore, if this is possible he asks you to
print which parentheses he should chose to get a valid sequence. A sequence of parentheses is valid if it is
empty or it can be written as (A) or AB where A and B are arbitrary valid sequences of parentheses.
Subtask 1 (10 points): \(1 \le n \le 10\)
Subtask 2 (10 points): \(z\)[\(a@@RISE_MATH_BLOCK_0@@i\)] for all \(i = 1\), 2, . . . n.
Subtask 3 (20 points): \(b@@RISE_MATH_BLOCK_1@@i + 1\) for all \(i = 1\), 2, . . . n.
Subtask 4 (70 points): No additional constraints. 1 sekun\(da / 512\) M\(iB / 110\) points
The first line contains an integer \(t\) (\(1 \le t \le 100\,000\)), number of parentheses sequences. \(t\) sequence
descriptions follow.
The first line of sequence description contains an integer \(n\) (\(1 \le n \le 100\,000\)), number of pairs of
parentheses in the sequence.
The second line contains \(z\), a string of length 2\(n\). \(z\) contains exclusively characters ( and ).
The following \(n\) lines of sequence description contain two integers \(a@@RISE_MATH_BLOCK_0@@i\) (\(1 \le a@@RISE_MATH_BLOCK_1@@i \le 2\)\(n\)). Each of
the numbers 1, 2, . . . 2\(n\) appears exactly once.
Sum of all \(n\) will be less than or equal to 100 000.
In the \(i-th\) of \(t\) lines print a sequence of zeros and ones representing a possible choice of parentheses. If
parenthesis at index \(a@@RISE_MATH_BLOCK_0@@j\) is chosen, print 1. If there is no valid sequence of parentheses pri\(nt -1\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(1 \le n \le 10\) |
2 | 10점 | \(z\)[\(a@@RISE_MATH_BLOCK_0@@i\)] for all \(i = 1\), 2, . . . n. |
3 | 20점 | \(b@@RISE_MATH_BLOCK_0@@i + 1\) for all \(i = 1\), 2, . . . n. |
4 | 70점 | No additional constraints. 1 sekun\(da / 512\) M\(iB / 110\) points |
1
4
()))((()
1 2
3 5
4 6
7 80 1 0 11
4
)()()()(
1 2
3 4
5 6
7 81 1 0 01
3
(()())
1 6
2 4
3 5-1Clarification of the first example:
From the original sequence ()))(((), only the bolded parentheses will remain ()))(((). That is ()(),
which is a valid sequence of parentheses.
Clarification of the second example:
From the original sequence )()()()(, only the bolded parentheses will remain )()()()(. That is (()),
which is a valid sequence of parentheses.
평가 및 의견
Superpozicija
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Superpozicija