| | In this problem your task is to simulate a message dispatching system in a most efficient way.
The system consists of a set of channels (identified by 64-bit ID numbers) and a set of listeners
(identified by 32-bit ID numbers).
Each listener can be subscribed to a set of channels.
The incoming messages are sent to some subset of channels and forwarded to listeners
who are subscribed to at least one of these channels.
Incoming events
The system must handle three types of incoming events:
-
incoming message consists of its content and a set of channel IDs it is sent to.
-
listener subscription consists of listener ID and a range of channel IDs [A, B],
meaning that channels with IDs between A and B, inclusive, are added to the set of channels this listener is subscribed to.
-
listener unsubscription consists of listener ID and a range of channel IDs [A, B],
meaning that channels with IDs between A and B, inclusive, are removed from the set of channels this listener is subscribed to.
Input format
You will be given a int[] x, which should be treated as unsigned integers and
can be converted to the sequence of incoming events using the following pseudocode:
for (i=0; i<N; i++)
{ if (x[i] > 0)
{ //incoming message
content = x[i];
n_channels = x[++i];
for (j = 0; j<n_channels; j++)
channels[j] = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
incoming_message(content, n_channels, channels);
}
else
if (x[i] == -1)
{ //listener subscription
listener = x[++i];
A = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
B = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
listener_subscription(listener, A, B);
}
else
if (x[i] == -2)
{ //listener unsubscription
listener = x[++i];
A = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
B = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
listener_unsubscription(listener, A, B);
}
}
Output format
You must return a int[] representing the sequence of outgoing events
initiated by the given sequence of incoming events. There are five types of outgoing events,
and each of them is described with a sequence of integers in the following way:
-
message delivery is described with a pair (listener ID, message content). Note that each
listener should receive a particular message only once (per incoming event) even if it is subscribed to several of the channels
the message is being sent to.
-
for listener subscription and listener unsubscription the first integer in the sequence
should be -1 or -2, respectively, followed by listener ID and four integers (Ahigh, Alow, Bhigh, Blow),
indicating that this listener subscribed to or unsubscribed from a range [A, B] of channel IDs.
These events should be initiated only by actual changes in the current subscriptions.
Thus, if a listener subscribes to the same channel ID twice, the event should be initiated only for
the first subscription (unless the listener has unsubscribed between the subscriptions).
Unsubscription from a channel which didn't belong to subscription set before shouldn't initiate an outgoing event as well.
-
for channel subscription and channel unsubscription the first integer in the sequence
should be -3 or -4, respectively, followed by four integers (Ahigh, Alow, Bhigh, Blow),
representing a range [A, B] of channels which had no listeners before and got their first listener,
or lost their last listener.
Each channel ID in the output is represented with a pair of integers in a same way as in input:
A = (((unsigned long long)Ahigh)<<32) | ((unsigned long long)Alow)
Scoring
First of all, your return will be checked for correctness.
This will be done by comparing the sequence of outgoing events to a precomputed reference one.
Note that in most cases the correct sequence of events can be written in several ways.
Thus, if one incoming event initiates several outgoing events, the order in which they are
mentioned in the sequence is not important, as long as all events initiated by earlier imcoming events
are mentioned before the events initiated by later incoming events.
Besides, ranges of channel IDs can be given as any set of non-intersecting ranges as long as they
combine to the reference set of ranges.
If your return is correct, the score for this test case will be the execution time in milliseconds,
otherwise the score will be 0.
Your overall score will be computed by finding the minimum time out of all submissions, MIN, for each test case. If your time for a testcase was YOU, that test will contribute MIN/YOU to your final score.
A tester is available for checking the correctness of your return offline. |