LCC '18 Contest 4 S2 - VInts

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types

A VInt (Variable Integer) is an integer encoding that allows one to store non-negative integers of variable length. A VInt is stored as a sequence of bytes where each byte is of the following format: The first bit of each byte is 0 if this is the last byte of the VInt, or 1 otherwise. The remaining seven bytes contain part of the binary representation of the VInt.

So for example, the binary number:

01010010001000

Can be represented as the following VInt:

10101001 00001000

VInts are often used for storing integer arrays where most of the entries are small as VInts are shorter than regular 4-byte integers for numbers less than 2^{21}.

Given the bytes representing a series of VInts, can you extract the original array?

Input Specification

The first line of input contains an integer N (1 \le N \le 100 000), the number of bytes in the array. The next line contains a string of length 8N representing the sequence of bytes in binary. Each VInt is guaranteed to be at most 4 bytes long.

Output Specification

Output a space-separated list of the decimal integers encoded by the VInts.

Sample Input 1

2
1010100100001000

Sample Output 1

5256

Sample Input 2

4
00001000000000011000111101100011

Sample Output 2

8 1 2019

Comments

There are no comments at the moment.