Four Subsequence Permutation Split

This is an Agentics migration of Frontier-CS algorithmic problem 227.

Your submitted zip_project run command is executed once per case. It receives exactly one case on stdin and must write the candidate answer to stdout. Do not read or write challenge-owned files. Network access is unavailable during setup, build, and run.

The trusted separated evaluator uses the original Frontier-CS Testlib checker. Public validation is intentionally small and only checks the interface. Official scoring uses the private Frontier-CS-derived run manifest.

Original Statement

Given a permutation $p$ of length $n$, you need to divide it into four disjoint subsequences $a$ $b$ $c$ $d$ such that the sum of $\operatorname{LIS}(a) + \operatorname{LDS}(b) + \operatorname{LIS}(c) + \operatorname{LDS}(d)$ is maximized.

• $\operatorname{LIS}(a)$ is the length of the Longest Increasing Subsequence (LIS) of $a$.
• $\operatorname{LDS}(b)$ is the length of the Longest Decreasing Subsequence (LDS) of $b$.

A permutation of length $n$ is a sequence that contains every integer from $1$ to $n$ exactly once.

A subsequence of a sequence is a sequence formed by deleting any number of elements (including zero or all elements) while maintaining the order of the remaining elements. The subsequences $a$ and $b$ are disjoint, meaning they do not share any elements.

Input format

• The first line contains an integer $n$, the length of the permutation $p$.
• The second line contains $n$ integers $p_1, p_2, p_3, \dots, p_n$, the permutation $p$.

Output format

• The first line contains four integers $r, s, p, q$, the lengths of the subsequences $a, b, c, d$.
• The second line contains $r$ integers $a_1, a_2, a_3, \dots, a_r$, the subsequence $a$.
• The third line contains $s$ integers $b_1, b_2, b_3, \dots, b_s$, the subsequence $b$.
• The fourth line contains $p$ integers $c_1, c_2, c_3, \dots, c_p$, the subsequence $c$.
• The fifth line contains $q$ integers $d_1, d_2, d_3, \dots, d_q$, the subsequence $d$.
• $r, s, p, q$ must satisfy $r + s + p + q = n$
• $a, b, c, d$ must be disjoint subsequences of $p$

Constraints

• $1 \leq n \leq 100000$
• $p$ is a permutation of length $n$

Scoring

• If your output is invalid, your score is 0.

• Otherwise, let $a, b, c, d$ be the lengths of the subsequences $a, b, c, d$ and $n$ be the length of the permutation $p$. Your score is equal to:

  $\operatorname{LIS}(a) + \operatorname{LDS}(b) + \operatorname{LIS}(c) + \operatorname{LDS}(d)$ / $n$