Олимпиадный тренинг

Задача . D. Обратная сумма сортировки


Задача

Темы: два указателя жадные алгоритмы Конструктив математика реализация Структуры данных *1900

Представим, что у вас был массив \(A\) из \(n\) элементов, каждый из которых это \(0\) или \(1\).

Определим функцию \(f(k,A)\), которая возвращает массив \(B\), который является результатом сортировки первых \(k\) элементов массива \(A\) в неубывающем порядке. Например, \(f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]\). Обратите внимание, что первые \(4\) элемента были отсортированы.

Рассмотрим массивы \(B_1, B_2,\ldots, B_n\), равные \(f(1,A), f(2,A),\ldots,f(n,A)\). Пусть \(C\) — массив, равный поэлементной сумме массивов \(B_1, B_2,\ldots, B_n\).

Например, пусть \(A=[0,1,0,1]\). Тогда \(B_1=[0,1,0,1]\), \(B_2=[0,1,0,1]\), \(B_3=[0,0,1,1]\), \(B_4=[0,0,1,1]\). Тогда \(C=B_1+B_2+B_3+B_4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]\).

Вам дан массив \(C\). Найдите бинарный массив \(A\) такой, что, если его обработать как описано выше, то получится данный массив \(C\). Гарантируется, что такой массив \(A\) существует для данного \(C\).

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \leq t \leq 1000\)) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. Первая строка содержит одно целое число \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)).

Вторая строка содержит \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(0 \leq c_i \leq n\)). Гарантируется, что для данного массива \(C\) существует подходящий массив \(A\).

Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(a_i\) равно \(0\) или \(1\)). Если существуют несколько ответов, выведите любой.

Примечание

Рассмотрим первый пример. Начнем с массива \(A=[1,1,0,1]\) и построим массивы \(B_i\):

  • \(B_1=[\color{blue}{1},1,0,1]\);
  • \(B_2=[\color{blue}{1},\color{blue}{1},0,1]\);
  • \(B_3=[\color{blue}{0},\color{blue}{1},\color{blue}{1},1]\);
  • \(B_4=[\color{blue}{0},\color{blue}{1},\color{blue}{1},\color{blue}{1}]\)
Затем просуммируем каждый столбик и получим \(C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]\).

Примеры
№Входные данныеВыходные данные
1 5
4
2 4 2 4
7
0 3 4 2 3 2 7
3
0 0 0
4
0 0 0 4
3
1 2 3 
1 1 0 1 
0 1 1 0 0 0 1 
0 0 0 
0 0 0 1 
1 0 1

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет