PIB '20 P3 - Rulebreaker

View as PDF

Points: 7 (partial)
Time limit: 0.5s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

John has an on-going contest with some of his friends. The problem is that they constantly find loopholes to exploit John's contest, so John has to make some new rules, but sometimes John's friends find loopholes to those rules. Then, he'll make new rules to overrule those rules.

In essence, John has a list of rules, each being able to do two operations:

1. Create a new rule.
2. Create a new rule to not follow the previous rule that was created.

After a while, John's friends get confused of which rule to follow, and so they come to ask you for help. They will give you queries of one of the following forms:

• 1 Create a new rule. It is guaranteed the first query will always be of this type.
• 2 Create a new rule to not follow the previous rule that was created.
• 3 x Output whether John's friends should follow the rule that was created or not. It is guaranteed , where is the number of rules that has been created so far. is one indexed.

Note: Rules that are created later are given higher priority in determining which rules to follow.

For example, if the following queries were given:

1. Create a rule.
2. Create a rule to not follow the previous rule.
3. Create a rule.
4. Create a rule to not follow the previous rule.

In this case, rules and would not be followed and rules and will be followed.

Note: Python users are recommmended to use CPython over PyPy and add the following the line to the top of the their solution for performance purposes: input = sys.stdin.readline.

Input Specification

The first line will contain the integer , the number of queries.

The next lines will each contain a query as defined above.

Output Specification

For each type 3 query, output 1 if John's friends should follow rule and 0 otherwise on its own line.

No further constraints.

5
1
2
3 1
2
3 1

0
1

Explanation For Sample For Subtask 1

1. Create a new rule, indexed 1.
2. Create a new rule, indexed 2, to not follow the previous rule (rule 1). Currently, John's friends should follow rule 2 and not follow rule 1.
3. Query if rule 1 should be followed - it should not. Therefore, 0 is outputted.
4. Create a new rule, indexed 3, to not follow the previous rule (rule 2). This means John's friends should follow rules 1 and 3 but not rule 2.
5. Query if rule 1 should be followed - it should. Therefore, 1 is outputted.

101
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3 2
3 3

0
1