Loading problem...

Preparing the statement, recent submissions, and submit form.

DOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord-backed certification.

Problems

Problems Categories

Community

Contests Ranking Board Notices Host an external contest Guide

Account

Policy

#644 Magic Contest

Problem#644

Magic Contest

magiccontest

[0]

DOJ/Grand Contest DOJ/GCD 1/Div1

DOJ/Grand Contest DOJ/GCD 1/Div2

Authors: rladbeka

Time limit: 4000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Grader mode: MANAGER_MULTI_RUN
Solve threshold: 100

Statement

Statement language

This is a two-step problem.

Alice and Bob are famous magicians. Together with their assistant Catherine, they decide to perform the following trick at a magic contest.

First, Bob enters a room and loses all contact with the outside. He can communicate only with Catherine. Catherine tells Alice a binary string $S$ of length $N$ .
Alice creates a binary string whose length is between $N$ and $2N+100$ , inclusive, and gives it to Catherine.

Editorial

View editorial

You must log in to submit.

Judge status Problem board

100

Catherine inserts one character, either 0 or 1, at an arbitrary position of the string and gives the resulting string to Bob.

Bob must recover the original string

S

from the string he receives.

Input

The input of the first execution is given in the following format.

0 $T$ $N_1$ $S_1$ $N_2$ $S_2$ $\vdots$ $N_T$ $S_T$

The input of the second execution is given in the following format.

1 $T$ $N_1\ L_1$ $P_1$

Output

In the first execution, print one binary string for Catherine on each of $T$ lines.

If the length printed for the $i$ -th test case is $M_i$ , it must satisfy $N_i\leq M_i\leq 2N_i+100$ .

In the second execution, print the original string $S_i$ for each test case in the order given in the input, one string per line.

Constraints

$1\leq T\leq 1\,000$ .
$1\leq N_i\leq 200\,000$ ( $1\leq i\leq T$ ).
$S_i$ is a binary string of length $N_i$ ( $1\leq i\leq T$ ).
$\sum_{i=1}^{T}N_i\leq 200\,000$ .
If $M_i$ is the length printed in the $i$ -th test case of the first execution, then $N_i\leq M_i\leq 2N_i+100$ ().
In the second execution, $L_i=M_i+1$ ( $1\leq i\leq T$ ).
$P_i$ is a binary string of length $L_i$ ( $1\leq i\leq T$ ).
Each $P_i$ is obtained by inserting one bit at an arbitrary position of the corresponding string from the first execution ( $1\leq i\leq T$ ).

Scoring

Bob must correctly recover the original string $S$ for every test case. If any string is not recovered correctly, the submission receives $0$ points.

Otherwise, the score depends on the lengths of the strings printed by Alice. For the $i$ -th test case, let $N_i$ be the original length and let $M_i$ be the length printed by Alice. Define $D_i$ as follows.

D_i=\max(M_i-N_i,20)

The score $Q_i$ of the $i$ -th test case is

Q_i=\max\left(0,100-70\sqrt{\cfrac{\log(D_i/20)}{\log(1+N_i/20)}}\right).

The base of the logarithm does not affect the score. The final score is the minimum $Q_i$ over all test cases in all private judge tests.

In particular, $M_i\leq N_i+20$ gives $100$ points for that test case. The formula is well-defined even for small .

Subtasks

#	Score	Constraints
1	100	No additional constraints.

N_2\ L_2

P_2

\vdots

N_T\ L_T

P_T

≤

Mi≤

2Ni+

100

1\leq i\leq T

≤

)

100

−

log(1+Ni/20)log(Di/20)

N_{i}

N_i

N_{i}