"""Локальные тесты домашнего задания 3.

Положите этот файл рядом с ноутбуком и в ячейке решения:

    from lab03_hw_tests import test_task1

Решение — функция без аргументов: читает данные через ``input()``
и печатает ответ через ``print()``, как в контесте.

    def task1():
        n = int(input())
        print(...)

    test_task1(task1)

Мелкие тесты (примеры, края, антитесты) лежат текстом. Большие —
собираются при прогоне из seed, без эталонных решений в файле.
Для задач 2, 3 и 5 ответ проверяется по свойствам, не сравнением строк.
"""

from __future__ import annotations

import builtins
import io
import random
import signal
import sys
import traceback
from collections import defaultdict

try:
    from tqdm.auto import tqdm
except ImportError:
    def tqdm(iterable, **kwargs):
        return iterable

_TIME_LIMIT = 2.0

_TITLES = {
    "1": "Нарушения неубывания",
    "2": "Порядок по модулю",
    "3": "По последней цифре",
    "4": "k-й по неубыванию",
    "5": "Точки",
}

_KINDS = {
    "1": "int",
    "2": "int_seq",
    "3": "int_seq",
    "4": "int",
    "5": "lines",
}

_MANUALS = {
    "1": [
        ("5\n1 2 2 4 9\n", "0\n"),
        ("3\n7 7 7\n", "0\n"),
        ("5\n5 4 3 2 1\n", "4\n"),
        ("4\n1 3 2 4\n", "1\n"),
        ("1\n0\n", "0\n"),
        ("4\n-5 -1 -1 3\n", "0\n"),
        ("3\n-1 -3 0\n", "1\n"),
        ("2\n1 0\n", "1\n"),
        ("2\n1000000000 -1000000000\n", "1\n"),
        ("20\n" + " ".join(map(str, range(20))) + "\n", "0\n"),
        ("20\n" + " ".join(map(str, range(20, 0, -1))) + "\n", "19\n"),
    ],
    "2": [
        ("5\n5 -2 2 -5 0\n", ""),
        ("2\n-3 3\n", ""),
        ("3\n0 0 0\n", ""),
        ("1\n7\n", ""),
        ("3\n3 2 1\n", ""),
        ("3\n-1 -2 -3\n", ""),
        ("4\n5 -5 5 -5\n", ""),
        ("3\n100 -100 0\n", ""),
        ("3\n1000000000 -1000000000 1000000000\n", ""),
        ("21\n" + " ".join(map(str, range(-10, 11))) + "\n", ""),
    ],
    "3": [
        ("3\n12 23 34\n", ""),
        ("3\n25 5 15\n", ""),
        ("3\n10 20 30\n", ""),
        ("1\n0\n", ""),
        ("3\n7 17 27\n", ""),
        ("4\n101 22 3 14\n", ""),
        ("5\n9 19 8 18 7\n", ""),
        ("4\n100 0 10 20\n", ""),
        ("5\n111 21 31 1 41\n", ""),
        ("5\n6 16 26 36 46\n", ""),
    ],
    "4": [
        ("6 4\n3 1 3 2 1 3\n", "3\n"),
        ("5 1\n7 7 7 7 7\n", "7\n"),
        ("5 5\n7 7 7 7 7\n", "7\n"),
        ("4 3\n0 1000 0 5\n", "5\n"),
        ("5 5\n4 1 4 2 4\n", "4\n"),
        ("1 1\n0\n", "0\n"),
        ("1001 1\n" + " ".join(map(str, range(1001))) + "\n", "0\n"),
        ("1001 1001\n" + " ".join(map(str, range(1001))) + "\n", "1000\n"),
        ("1001 501\n" + " ".join(map(str, range(1001))) + "\n", "500\n"),
        ("20 1\n" + " ".join(["0", "1000"] * 10) + "\n", "0\n"),
        ("20 20\n" + " ".join(["0", "1000"] * 10) + "\n", "1000\n"),
        ("16 8\n" + " ".join(["5"] * 8 + ["6"] * 8) + "\n", "5\n"),
        ("16 9\n" + " ".join(["5"] * 8 + ["6"] * 8) + "\n", "6\n"),
    ],
    "5": [
        ("3\n3 1\n1 2\n2 0\n", ""),
        ("2\n1 5\n1 2\n", ""),
        ("3\n2 3\n2 1\n1 9\n", ""),
        ("1\n0 0\n", ""),
        ("3\n5 5\n4 4\n3 3\n", ""),
        ("3\n-1 10\n-1 -5\n0 0\n", ""),
        ("3\n2 2\n2 2\n1 1\n", ""),
        ("2\n1000000000 -1000000000\n-1000000000 1000000000\n", ""),
        ("20\n" + "\n".join("1 %d" % (20 - i) for i in range(20)) + "\n", ""),
    ],
}

# Крупные и средние: (вид, ...параметры). Ответы задач 1 и 4 посчитаны заранее.
_GEN = {
    "1": [
        ("spike80",),
        ("rand", 1711, 100, -50, 50, 49),
        ("rand", 1712, 500, -10 ** 6, 10 ** 6, 252),
        ("rand", 1713, 3000, -10 ** 9, 10 ** 9, 1512),
        ("const", 20000, 7, 0),
        ("desc", 20000, 19999),
        ("rand", 1714, 20000, -10 ** 9, 10 ** 9, 10000),
        ("rand", 1715, 200000, -10 ** 9, 10 ** 9, 100038),
    ],
    "2": [
        ("rand", 1721, 40, -20, 20),
        ("rand", 1722, 200, -1000, 1000),
        ("rand", 1723, 2000, -10 ** 6, 10 ** 6),
        ("rand", 1724, 20000, -10 ** 9, 10 ** 9),
        ("rand", 1725, 100000, -10 ** 9, 10 ** 9),
    ],
    "3": [
        ("digit_rev", 9),
        ("rand", 1731, 40, 99),
        ("rand", 1732, 200, 10 ** 6),
        ("rand", 1733, 2000, 10 ** 9),
        ("digit_rev", 1999),
        ("rand", 1734, 20000, 10 ** 9),
        ("digit_rev", 9999),
        ("rand", 1735, 100000, 10 ** 9),
    ],
    "4": [
        ("rand", 1741, 80, 40, 449),
        ("rand", 1742, 500, 1, 2),
        ("rand", 1743, 500, 500, 1000),
        ("rand", 1744, 3000, 1500, 503),
        ("alt", 20000, 10000, 0),
        ("alt", 20000, 10001, 1000),
        ("rand", 1745, 20000, 7777, 386),
        ("const", 200000, 7, 1, 7),
        ("rand", 1746, 200000, 100000, 499),
    ],
    "5": [
        ("rand", 1751, 40, 8),
        ("rand", 1752, 200, 20),
        ("rand", 1753, 2000, 50),
        ("same_x_desc", 20000),
        ("rand", 1754, 20000, 100),
        ("rand", 1755, 100000, 200),
    ],
}


def _rand_list(seed, n, lo, hi):
    rng = random.Random(seed)
    return [rng.randint(lo, hi) for _ in range(n)]


def _stdin_array(a):
    return "%d\n%s\n" % (len(a), " ".join(map(str, a)))


def _stdin_array_k(a, k):
    return "%d %d\n%s\n" % (len(a), k, " ".join(map(str, a)))


def _stdin_points(points):
    parts = ["%d" % len(points)]
    parts.extend("%d %d" % xy for xy in points)
    return "\n".join(parts) + "\n"


def _make_case(task_id, spec):
    kind = spec[0]
    if task_id == "1":
        if kind == "spike80":
            a = list(range(80))
            a[40] = 10 ** 9
            a[41] = -(10 ** 9)
            return _stdin_array(a), "1\n"
        if kind == "rand":
            _, seed, n, lo, hi, ans = spec
            return _stdin_array(_rand_list(seed, n, lo, hi)), "%d\n" % ans
        if kind == "const":
            _, n, value, ans = spec
            return _stdin_array([value] * n), "%d\n" % ans
        if kind == "desc":
            _, n, ans = spec
            return _stdin_array(list(range(n, 0, -1))), "%d\n" % ans
    if task_id == "2":
        _, seed, n, lo, hi = spec
        return _stdin_array(_rand_list(seed, n, lo, hi)), ""
    if task_id == "3":
        if kind == "digit_rev":
            _, m = spec
            a = []
            for d in range(10):
                a.extend(10 * i + d for i in range(m, -1, -1))
            return _stdin_array(a), ""
        _, seed, n, hi = spec
        return _stdin_array(_rand_list(seed, n, 0, hi)), ""
    if task_id == "4":
        if kind == "rand":
            _, seed, n, k, ans = spec
            return _stdin_array_k(_rand_list(seed, n, 0, 1000), k), "%d\n" % ans
        if kind == "const":
            _, n, value, k, ans = spec
            return _stdin_array_k([value] * n, k), "%d\n" % ans
        if kind == "alt":
            _, n, k, ans = spec
            return _stdin_array_k([0, 1000] * (n // 2), k), "%d\n" % ans
    if task_id == "5":
        if kind == "same_x_desc":
            _, n = spec
            return _stdin_points([(1, n - i) for i in range(n)]), ""
        _, seed, n, n_x = spec
        rng = random.Random(seed)
        points = [(rng.randint(0, n_x - 1), rng.randint(-(10 ** 9), 10 ** 9))
                  for _ in range(n)]
        return _stdin_points(points), ""
    raise ValueError(spec)


def _iter_cases(task_id):
    for pair in _MANUALS[task_id]:
        yield pair
    for spec in _GEN[task_id]:
        yield _make_case(task_id, spec)


def _n_cases(task_id):
    return len(_MANUALS[task_id]) + len(_GEN[task_id])


class _TestTimeout(BaseException):
    """Прерывание по лимиту времени; не ловится через except Exception."""


def _normalize(kind: str, text: str) -> str:
    text = text.replace("\r\n", "\n").strip()
    if kind == "yesno":
        return text.upper()
    if kind == "int":
        return str(int(text))
    if kind == "int_seq":
        return " ".join(text.split())
    if kind == "lines":
        return "\n".join(line.strip() for line in text.splitlines() if line.strip())
    if kind == "tokens":
        return " ".join(text.split())
    if kind == "word":
        return text.split()[0] if text else ""
    return text


def _check_abs_order(stdin_text: str, stdout_text: str) -> str | None:
    lines = [ln for ln in stdin_text.replace("\r\n", "\n").split("\n") if ln.strip()]
    n = int(lines[0])
    src = list(map(int, lines[1].split()))
    tokens = stdout_text.replace("\r\n", "\n").split()
    if len(tokens) != n:
        return "нужно n целых чисел"
    try:
        out = [int(x) for x in tokens]
    except ValueError:
        return "ответ должен состоять из целых чисел"
    if sorted(out) != sorted(src):
        return "выход должен быть перестановкой входа"
    for i in range(n - 1):
        if (abs(out[i]), out[i]) > (abs(out[i + 1]), out[i + 1]):
            return "порядок: по |a|, при равных модулях — по самому числу"
    return None


def _check_last_digit(stdin_text: str, stdout_text: str) -> str | None:
    lines = [ln for ln in stdin_text.replace("\r\n", "\n").split("\n") if ln.strip()]
    n = int(lines[0])
    src = list(map(int, lines[1].split()))
    tokens = stdout_text.replace("\r\n", "\n").split()
    if len(tokens) != n:
        return "нужно n целых чисел"
    try:
        out = [int(x) for x in tokens]
    except ValueError:
        return "ответ должен состоять из целых чисел"
    if sorted(out) != sorted(src):
        return "выход должен быть перестановкой входа"
    for i in range(n - 1):
        if out[i] % 10 > out[i + 1] % 10:
            return "последние цифры должны идти по неубыванию"
    need = defaultdict(list)
    got = defaultdict(list)
    for x in src:
        need[x % 10].append(x)
    for x in out:
        got[x % 10].append(x)
    if need != got:
        return "при равной последней цифре порядок как во входе"
    return None


def _check_points_xy(stdin_text: str, stdout_text: str) -> str | None:
    lines = [ln for ln in stdin_text.replace("\r\n", "\n").split("\n") if ln.strip()]
    n = int(lines[0])
    src = []
    for i in range(n):
        x, y = map(int, lines[i + 1].split())
        src.append((x, y))
    tokens = stdout_text.replace("\r\n", "\n").split()
    if len(tokens) != 2 * n:
        return "нужно n строк вида x y"
    try:
        out = []
        for i in range(n):
            out.append((int(tokens[2 * i]), int(tokens[2 * i + 1])))
    except ValueError:
        return "x и y должны быть целыми"
    if sorted(out) != sorted(src):
        return "выход должен быть перестановкой входа"
    for i in range(n - 1):
        if out[i] > out[i + 1]:
            return "точки должны идти по неубыванию (x, y)"
    return None


_CHECKERS = {
    "2": _check_abs_order,
    "3": _check_last_digit,
    "5": _check_points_xy,
}


def _invoke(fn, stdin_text: str) -> str:
    buf_in = io.StringIO(stdin_text if stdin_text.endswith("\n") else stdin_text + "\n")
    buf_out = io.StringIO()
    real_print = builtins.print

    def fake_input(prompt=""):
        line = buf_in.readline()
        if line == "":
            raise EOFError("EOF when reading a line")
        return line[:-1] if line.endswith("\n") else line

    def fake_print(*args, **kwargs):
        kwargs.setdefault("file", buf_out)
        return real_print(*args, **kwargs)

    patches = [
        (sys, "stdin", buf_in),
        (sys, "stdout", buf_out),
        (builtins, "input", fake_input),
        (builtins, "print", fake_print),
    ]
    g = getattr(fn, "__globals__", None)
    if isinstance(g, dict):
        patches.append((g, "input", fake_input))
        patches.append((g, "print", fake_print))

    missing = object()
    old = [(ns, key, ns.get(key, missing) if isinstance(ns, dict) else getattr(ns, key, missing))
           for ns, key, _ in patches]

    def _on_alarm(signum, frame):
        raise _TestTimeout()

    prev_handler = None
    timer_set = False
    returned = None
    try:
        for ns, key, value in patches:
            if isinstance(ns, dict):
                ns[key] = value
            else:
                setattr(ns, key, value)
        if hasattr(signal, "setitimer"):
            prev_handler = signal.signal(signal.SIGALRM, _on_alarm)
            signal.setitimer(signal.ITIMER_REAL, _TIME_LIMIT)
            timer_set = True
        try:
            returned = fn()
        except SystemExit:
            pass
    finally:
        if timer_set:
            signal.setitimer(signal.ITIMER_REAL, 0.0)
            if prev_handler is not None:
                signal.signal(signal.SIGALRM, prev_handler)
        for ns, key, value in old:
            if value is missing:
                if isinstance(ns, dict):
                    ns.pop(key, None)
                elif hasattr(ns, key):
                    delattr(ns, key)
            elif isinstance(ns, dict):
                ns[key] = value
            else:
                setattr(ns, key, value)
    out = buf_out.getvalue()
    if not out.strip() and returned is not None:
        out = str(returned)
    return out


def _preview(text: str, limit: int = 400) -> str:
    text = text if text.endswith("\n") else text + "\n"
    if len(text) <= limit:
        return text
    return text[:limit] + "\n...\n"


def _run(task_id: str, fn) -> bool:
    if not callable(fn):
        raise TypeError("ожидалась функция без аргументов, например def task(): ...")
    kind = _KINDS[task_id]
    title = _TITLES[task_id]
    checker = _CHECKERS.get(task_id)
    total = _n_cases(task_id)
    ok = 0
    first_fail = None
    for i, (stdin, expected) in enumerate(tqdm(_iter_cases(task_id), total=total,
                                               desc=f"task{task_id}", leave=False), start=1):
        try:
            got = _invoke(fn, stdin)
            if checker is not None:
                reason = checker(stdin, got)
                good = reason is None
            else:
                reason = None
                good = _normalize(kind, got) == _normalize(kind, expected)
            if good:
                ok += 1
            elif first_fail is None:
                if checker is not None:
                    first_fail = (
                        f"WA на тесте {i}/{total}\n"
                        f"вход:\n{_preview(stdin)}"
                        f"получено: {_normalize(kind, got)!r}\n"
                        f"{reason}"
                    )
                else:
                    first_fail = (
                        f"WA на тесте {i}/{total}\n"
                        f"вход:\n{_preview(stdin)}"
                        f"ожидалось: {_normalize(kind, expected)!r}\n"
                        f"получено:  {_normalize(kind, got)!r}"
                    )
        except _TestTimeout:
            if first_fail is None:
                first_fail = (
                    f"TLE на тесте {i}/{total} "
                    f"(лимит {int(_TIME_LIMIT)} с)\n"
                    f"вход:\n{_preview(stdin)}"
                    "решение работает слишком долго"
                )
        except Exception:
            if first_fail is None:
                first_fail = (
                    f"RE на тесте {i}/{total}\n"
                    f"вход:\n{_preview(stdin)}"
                    f"{traceback.format_exc()}"
                )
    name = f"task{task_id} «{title}»"
    if first_fail is None:
        print(f"{name}: {ok}/{total} OK")
        return True
    print(f"{name}: {ok}/{total} не OK")
    print(first_fail)
    return False


def test_task1(fn):
    """Нарушения неубывания."""
    return _run("1", fn)


def test_task2(fn):
    """Порядок по модулю."""
    return _run("2", fn)


def test_task3(fn):
    """По последней цифре."""
    return _run("3", fn)


def test_task4(fn):
    """k-й по неубыванию."""
    return _run("4", fn)


def test_task5(fn):
    """Точки."""
    return _run("5", fn)


test_adjacent_inversions = test_task1
test_sort_by_abs = test_task2
test_last_digit_order = test_task3
test_kth_small_range = test_task4
test_points_xy = test_task5

__all__ = [
    "test_task1",
    "test_task2",
    "test_task3",
    "test_task4",
    "test_task5",
]