Циклические скобки
Дана строка $S$, состоящая из $k$ видов пар скобок. Каждая скобка имеет вид $t$ — целое число, такое что $1 \leq |t| \leq k$. Если скобка имеет вид $t$, то
- Если $t$ > 0, то это открывающая скобка типа $t$.
- Если $t$ < 0, то это закрывающая скобка типа $-t$.
Таким образом, всего существует $k$ типов пар скобок.
Напомним определение правильной скобочной последовательности:
- Пустая последовательность является правильной.
- Если $A$ и $B$ - две правильные скобочные последовательности, то их конкатенация $« AB»$ тоже является правильной скобочной последовательностью.
- Если $A$ - правильная скобочная последовательность, $c \ (1\leq c \leq k)$ — некоторый тип скобок, то последовательность $«c\ \ A\ \ {-c}»$ тоже является правильной.
Циклический сдвиг скобочной последовательности вправо на $m$ > 1 эквивалентен $m$ циклическим сдвигам на 1.
Найдите все такие $m \ (0 \leq m \leq |S| - 1) $, что при циклическом сдвиге на $m$ элементов получившаяся скобочная последовательность будет правильной.
В первой строке дано целое число $n \ (1 \leq n \leq 1 \ 000 \ 000)$ — длина строки.
Во второй строке дана строка $s$ длиной $n$ символов — $n$ целых чисел $s_1, \ s_2, \ ..., \ s_n \ (1 \leq |s_i| \leq 10^9)$.
В первой строке выведите количество сдвигов, которые дают правильную скобочную последовательность, в следующей строке выведите сами эти сдвиги в порядке возрастания.
| Группа | Баллы | Доп. ограничения | Необх. группы | Комментарий |
| $0$ | $0$ | — | — | Тесты из условия |
| $1$ | $7$ | $n \leq 500$, $k = 1$ | — | Каждый тест |
| $2$ | $10$ | $n \leq 5000$, $k = 1$ | — | Каждый тест |
| $3$ | $20$ | $k = 1$ | — | Каждый тест |
| $4$ | $26$ | $n \leq 5000$, $k \leq 10^9$ | — | Каждый тест |
| $5$ | $37$ | $k \leq 10^9$ | — | Каждый тест |
4 1 2 -1 -2
0
8 -2 2 2 -2 1 -1 -2 2
2 1 7
8 -1 -3 4 -4 -5 5 3 1
1 3
В первом тестовом примере все циклические сдвиги строки это:
- 1 2 -1 -2
- -2 1 2 -1
- -1 -2 1 2
- 2 -1 -2 1
Правильной скобочной последовательности среди них нет.
Во втором тестовом примере циклические сдвиги это 1 и 7:
- 2 -2 2 2 -2 1 -1 -2
- 2 2 -2 1 -1 -2 2 -2
Можно заметить, что других сдвигов, которые дают правильную скобочную последовательность нет.
Задача на Codeforces (контест gym/105151, задача E, © Codeforces.com)