BUREAU - Bureaucracy
Long ago, in a kingdom far, far away the king decided to keep a record of all laws of his kingdom. From that moment whenever a new law was passed, a corresponding record was added to the law archive.
Many centuries later lawyers discovered that there were only two types of laws in the kingdom:
- direct law, that states a new norm;
- canceling law, that cancels one of the previous laws.
The law is considered active if and only if there is no active law that cancels it.
You are to write program that finds out which laws are still active.
The first line of the input contains T, the number of test cases. T test cases follow.
The first line of each test case contains an integer number n (1 <= n <= 100000) - the number of passed laws.
The following n lines describe one law each. Each description has one of the following formats:
- "declare", meaning that a direct law was passed.
- "cancel i", where i is the number of law being cancelled by this one.
The laws are numbered from one.
For each test case your output must contain a line with the number of active laws. The following line must contain numbers of these laws listed in increasing order.
Input: 1 5 declare cancel 1 declare cancel 2 cancel 3 Output: 3 1 4 5
getting runtime error (SIGSEGV)
a law cannot be canceled before declaring it
" in a kingdom far, far away " -- is it taken from movie shrek !!! ??
can a law be canceled before actually declaring it
is the order of laws chronological ? ( can a law be canceled before actually declaring it ? )Last edit: 2011-08-05 18:40:22
@Fidel: Very nice problem :-) I loved it!
Is it possible to declare a law that has not been made? (i mean, that the first law for example is cancel 3)?
any ambiguous test cases possible?like
Marcelo Quiroz Alcocer:
my code works well tell me the final output is to jump online or not, even as it is t I added long long for support.
@[[soup_boy]]: it would obviously be paradoxical to do so, so the answer is "no"...Last edit: 2013-02-10 04:24:18