Помощь с логикой кода

Суть задачи: на вход подается:

  1. кол-во строк на ввод
  2. строка (из 0 и 1)
  3. число операций над строкой (замена элемента по номеру)
  4. операция (в формате: "номер" "символ")

оригинал: https://codeforces.com/problemset/problem/2036/C

сложность в ограничении по времени, но данный код ошибается на 550 токене на 2 тесте, не могу понять в чем проблема, пожалуйста, намекните на дыру в логике, заранее спасибо

int n = Convert.ToInt32(Console.ReadLine());
List<int> list1100 = new List<int>();
List<string> list = new List<string>();
bool result;
for (int i = 0; i < n; i++)
{
    char[] arr = Console.ReadLine().ToCharArray();
    Func(arr);
    int q = Convert.ToInt32(Console.ReadLine());
    for (int k = 0; k < q; k++)
    {
        string x = Console.ReadLine();
        if (arr.Length < 4)
        {
            list.Add("NO");
            continue;
        }

        string[] str = x.Split(' ');
        int index = Convert.ToInt32(str[0]);
        char value = Convert.ToChar(str[1]);

        result = list1100.Count > 0;
        if (value == arr[index - 1])
        {
            list.Add(result ? "YES" : "NO");
            continue;
        }

        arr[index - 1] = value;

        if (value == '1')
        {
            if (arr.Length > index + 2) // {input}100
            {
                if (arr[index] == '1' && arr[index + 1] == '0' && arr[index + 2] == '0') { if (!list1100.Contains(index - 1)) { list1100.Add(index - 1); } list.Add("YES"); continue; }
            }
            if (arr.Length >= index + 2 && index != 1) // 1{input}00
            {
                if (arr[index - 2] == '1' && arr[index] == '0' && arr[index + 1] == '0') { if (!list1100.Contains(index - 2)) { list1100.Add(index - 2); } list.Add("YES"); continue; }
            }
        }
        else // value == 0
        {
            if (arr.Length >= index + 1 && index >= 3) // 11{input}0
            {
                if (arr[index - 3] == '1' && arr[index - 2] == '1' && arr[index] == '0') { if (!list1100.Contains(index - 3)) { list1100.Add(index - 3); } list.Add("YES"); continue; }
            }
            if (arr.Length >= index && index >= 4) // 110{input}
            {
                if (arr[index - 4] == '1' && arr[index - 3] == '1' && arr[index - 2] == '0') { if (!list1100.Contains(index - 4)) { list1100.Add(index - 4); } list.Add("YES"); continue; }
            }
        }
        foreach (int ex in list1100)
        {
            if (ex <= index - 1 && index - 1 <= ex + 3)
            {
                list1100.Remove(ex);
                break;
            }
        }
        result = list1100.Count > 0;
        list.Add(result ? "YES" : "NO");
    }
}
for (int i = 0; i < list.Count; i++)
{
    Console.WriteLine(list[i]);
}

void Func(char[] arr)
{
    list1100.Clear();
    for (int j = 0; j < arr.Length - 3; j++)
    {
        if (arr[j] == '1' && arr[j + 1] == '1' && arr[j + 2] == '0' && arr[j + 3] == '0') { list1100.Add(j); }
    }
    return;
}

Ответы (1 шт):

Автор решения: Qwertiy

Строки 1100 не могут накладываться друг на друга. Каждое изменение может добавить или испортить только одну такую подстроку.

Считаем, сколько раз встречается подстрока в исходной строке.

Для каждого изменения:

  • до изменения проверяем, есть ли среди 4 подстрок, затрагивающих изменяемый символ 1100 - если есть, уменьшаем счётчик
  • после изменения проверяем снова и если есть, то увеличиваем
  • сравниваем с нулём и выводим соответствующий ответ

Асимптотика линейная. А у кода в вопросе - квадратичная.

PS: Даже если бы строки могли накладываться, решение могло бы быть аналогичным.

→ Ссылка