2g-no-more-nor-less.js

/*

G. Ни больше ни меньше

Ограничение времени	2 секунды (фактическое использование на тестах – до 116ms)
Ограничение памяти	256Mb (фактическое использование на тестах – до 17.82Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Дан массив целых положительных чисел a длины n. Разбейте его на минимально возможное количество отрезков, чтобы каждое число было не меньше длины отрезка которому оно принадлежит. Длиной отрезка считается количество чисел в нем.

Разбиение массива на отрезки считается корректным, если каждый элемент принадлежит ровно одному отрезку.

Формат ввода
Первая строка содержит одно целое число t (1 ≤ t ≤ 1000) — количество наборов тестовых данных. Затем следуют t наборов тестовых данных.
Первая строка набора тестовых данных содержит одно целое число n (1 ≤ n ≤ 10^5) — длину массива.
Следующая строка содержит n целых чисел a[1], a[2], …, a[n] (1 ≤ a[i] ≤ n) — массив a.
Гарантируется, что сумма n по всем наборам тестовых данных не превосходит 2 ⋅ 10^5.

Формат вывода
Для каждого набора тестовых данных в первой строке выведите число k — количество отрезков в вашем разбиении.
Затем в следующей строке выведите k чисел len[1], len[2], …, len[k]  — длины отрезков в порядке слева направо.

Пример

Ввод
3
5
1 3 3 3 2
16
1 9 8 7 6 7 8 9 9 9 9 9 9 9 9 9
7
7 2 3 4 3 2 7

Вывод
3
1 2 2
3
1 6 9 
3
2 3 2

Примечания
Ответы в примере соответствуют разбиениям:
{[1], [3, 3], [3, 2]}
{[1], [9, 8, 7, 6, 7, 8], [9, 9, 9, 9, 9, 9, 9, 9, 9]}
{[7, 2], [3, 4, 3], [2, 7]}
В первом наборе тестовых данных набор длин {1, 3, 1}, соответствующий разбиению {[1], [3, 3, 3], [2]}, также был бы корректным.

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim().split('\n');

const datasets = [];
let currentDatasetIndex = -1;

for (let i = 2; i < input.length; i = i + 2) {
    const rangeString = input[i].trim() + ' ';
    const rangeStringLength = rangeString.length;

    datasets.push([]);
    ++currentDatasetIndex;

    let number = 0;
    let valueString = '';
    let segmentLength = 0;
    let minSegmentPart = Infinity;

    for (let j = 0; j < rangeStringLength; ++j) {
        if (rangeString[j] === ' ') {
            number = parseInt(valueString);
            if (number <= segmentLength || minSegmentPart <= segmentLength) {
                datasets[currentDatasetIndex].push(segmentLength);
                minSegmentPart = number;
                segmentLength = 1;
            } else {
                if (number < minSegmentPart) {
                    minSegmentPart = number;
                }
                ++segmentLength;
            }
            valueString = '';
        } else {
            valueString += rangeString[j];
        }
    }
    datasets[currentDatasetIndex].push(segmentLength);

}

const output = datasets.map((dataset) => dataset.length + '\n' + dataset.join(' ')).join('\n');

fs.writeFileSync('output.txt', `${output}`);