Nothing much in this problem, just standard preparation: an exhaustive gen, a random gen, and a maxima gen for $$$n = 50$$$.

Maxima generator was done with the main idea of the solution in mind: the answer only depends on $$$\text{cnt}_1$$$, so iterate each such value, generate the desired amount for each array, and shuffle it.

namespace variables {
    const char* t = "t";
    const char* n = "n";
    const char* a = "a";
}

namespace limits {
    const int MIN_T = 1;
    const int MAX_T = 500;

    const int MIN_N = 1;
    const int MAX_N = 50;
    const int MIN_A = 0;
    const int MAX_A = 1;
}

#include <iostream>
#include "thresholds.h"
#include "testlib.h"
using namespace std;
 
int main(int argc, char *argv[]) {
    registerValidation(argc, argv);
    int t = inf.readInt(limits::MIN_T, limits::MAX_T, "~t");
    inf.readEoln();
 
    for (int testCase = 1; testCase <= t; testCase++) {
        setTestCase(testCase);
 
        int n = inf.readInt(limits::MIN_N, limits::MAX_N, variables::n);
        inf.readEoln();
        inf.readInts(n*2, limits::MIN_A, limits::MAX_A, variables::a);
        inf.readEoln();
    }
    inf.readEof();
    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.h"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int min_n  = limits::MIN_N;
    int max_n  = limits::MAX_N;
    
    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-min_n")) {
            min_n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_n")) {
            max_n = atoi(argv[++i]);
            continue;
        }
    }
    
    vector<vector<int>> arrays;
    
    for (int n = min_n; n <= max_n; n++) {
        for (int mask = 0; mask < (1 << (n * 2)); mask++) {
            vector<int> array(n * 2);
            
            for (int i = 0; i < n * 2; i++) {
                array[i] = (mask >> i) & 1;
            }
            
            arrays.emplace_back(array);
        }
    }

    cout << arrays.size() << endl;
    for (auto &array: arrays) {
        cout << array.size() / 2 << endl;
        println(array);
    }

    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.h"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int min_n  = limits::MIN_N;
    int max_n  = limits::MAX_N;
    int min_ai = limits::MIN_A;
    int max_ai = limits::MAX_A;

    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-min_n")) {
            min_n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_n")) {
            max_n = atoi(argv[++i]);
            continue;
        }
    }

    int t = limits::MAX_T;
    cout << t << endl;
    for (int _ = 0; _ < t; _++) {
        int n = rnd.next(min_n, max_n);
        cout << n << endl;
        for (int i = 0; i < n * 2; i++) {
            cout << rnd.next(min_ai, max_ai);
            if (i < n * 2 - 1) cout << " ";
            else cout << endl;
        }
    }

    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.h"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int n = limits::MAX_N;
    
    vector<vector<int>> arrays;
    arrays.emplace_back(vector<int>(n*2, 0));
    arrays.emplace_back(vector<int>(n*2, 1));
    
    int cycle_start = rnd.next(0, n*2-2);
    
    for (int t = 2; t < limits::MAX_T; t++) {
        vector<int> array(n * 2, 0);
        int cnt1 = (cycle_start + (t - 2)) % (n*2 - 1) + 1;
        
        for (int i = 0; i < cnt1; i++) {
            array[i] = 1;
        }
        
        shuffle(array.begin(), array.end());
        arrays.emplace_back(array);
    }

    shuffle(arrays.begin(), arrays.end());
    cout << arrays.size() << endl;
    for (auto &array: arrays) {
        cout << array.size() / 2 << endl;
        println(array);
    }

    return 0;
}

I mostly relied on echo for this one. It also used to have a generator_exhaustive.cpp, but Artyom replaced it with a more compact one.

namespace variables {
    const char* t = "t";
    const char* n = "n";
    const char* k = "k";
    const char* m = "m";
    const char* p_i = "p_i";
}
 
namespace limits {
    const int MIN_T = 1;
    const int MAX_T = 5000;
 
    const int MIN_N = 1;
    const int MAX_N = 199'999;
 
    const int MAX_SUM_N = 200'000;
}

#include "testlib.h"
#include "thresholds.h"
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
    registerValidation(argc, argv);
    int t = inf.readInt(limits::MIN_T, limits::MAX_T, variables::t);
    inf.readEoln();

    int sum_n = 0;

    for (int testCase = 1; testCase <= t; testCase++) {
        setTestCase(testCase);

        int n = inf.readInt(limits::MIN_N, limits::MAX_N, variables::n);
        ensuref(n % 2 == 1, "n must be odd");
        sum_n += n;
        ensuref(sum_n <= limits::MAX_SUM_N, "The sum of n over all test cases must not exceed %d", limits::MAX_SUM_N);
        inf.readSpace();
        int k = inf.readInt(1, n, variables::k);
        inf.readEoln();
    }
    
    inf.readEof();
    return 0;
}

#include "testlib.h"
#include "thresholds.h"
#include <iostream>

using namespace std;

int n, k;

int median(vector<int> &p) {
    // if (p.size() % 2 == 0) return false;

    // int last = 0;
    // for (int i=0; i<p.size(); i++) {
    //     if (!(last < p[i] && p[i] <= n)) return false;
    //     last = p[i];
    // }

    int midpoint = p.size() / 2;
    int l = p[midpoint];
    int r = (midpoint + 1 == p.size() ? n : p[midpoint + 1] - 1);

    return ((r + l) >> 1);
}

bool readAns(InStream &in) {
    // true=partition, false = -1
    int m = in.readInt(-1, n, variables::m);
    
    if (m == -1) return false;
    
    if (m == 0) in.quitf(_wa, "m cannot be 0");
    if (m % 2 == 0) in.quitf(_wa, "m cannot be even");
    
    vector<int> p(m);
    int last = 0;
    for (int i=0; i<m; i++) {
        int rbound = (i == 0 ? 1 : n);
        p[i] = in.readInt(last + 1, rbound, variables::p_i);
        if (last % 2 == p[i] % 2) in.quitf(_wa, "%d-th subarray has even length", i+1);
        last = p[i];
    }
    
    int med = median(p);
    if (med != k) in.quitf(_wa, "expected median %d but got %d", k, med);
    
    return true;
}

int main(int argc, char *argv[]) {
    registerTestlibCmd(argc, argv);

    int t = inf.readInt();
    
    for (int testCase=1; testCase<=t; testCase++) {
        setTestCase(testCase);

        n = inf.readInt();
        k = inf.readInt();
        
        bool ja = readAns(ans);
        bool pa = readAns(ouf);

        if (!pa && ja) {
            quitf(_wa, "participant has no answer, but jury does");
        }
        if (pa && !ja) {
            quitf(_fail, "participant gives correct median when jury has no answer");
        }
    }

    quitf(_ok, "%d test cases passed.", t);
}

#include "testlib.h"
#include "thresholds.h"
#include <iostream>

using namespace std;

using ll = long long;

map<string, string> params;

long long get(string name, long long def = 0) {
    if (params.count(name)) {
        return stoll(params[name]);
    } else {
        return def;
    }
}

int main(int argc, char *argv[]) {
    registerGen(argc, argv, 1);
    for (int i = 1; i < argc; i++) {
        string s = string(argv[i]);
        if (s.find("=") != string::npos) {
            auto pos = s.find("=");
            params[s.substr(0, pos)] = s.substr(pos + 1);
        } else {
            params[s] = "";
        }
    }
    int t = limits::MAX_T;
    vector<int> ns = rnd.partition(t, limits::MAX_SUM_N / 2);
    cout << t << "\n";
    for (int tc = 0; tc < t; tc++) {
        int n = 2 * ns[tc] - 1;
        int k = rnd.next(1, n);
        cout << n << " " << k << "\n";
    }
    return 0;
}

#include "testlib.h"
#include "thresholds.h"
#include <iostream>
#include <cassert>

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    assert(argc % 2 == 1);

    cout << (argc / 2) << endl;
    for (int index = 1; index < argc; index += 2) {
        cout << argv[index] << " " << argv[index + 1] << endl;
    }

    return 0;
}

This is a standard array problem to prepare. Some specific generators are used for benchmarking — here I relied on Fibonacci sequence for that purpose (though thinking again, I don't think either of them made any difference...).

Also, from here on we have thresholds.cpp. The naming wasn't really consistent, I'll fix that in my next round (if it ever comes).

namespace variables {
    const char* t = "t";
    const char* n = "n";
    const char* a = "a";
}

namespace limits {
    const int MIN_T = 1;
    const int MAX_T = 10'000;

    const int MIN_N = 3;
    const int MAX_N = 200'000;
    const int MIN_A = 1;
    const int MAX_A = 1'000'000'000;

    const int MAX_SUM_N = 200'000;
}

#include <iostream>
#include "thresholds.cpp"
#include "testlib.h"
using namespace std;
 
int main(int argc, char *argv[]) {
    registerValidation(argc, argv);
    int t = inf.readInt(limits::MIN_T, limits::MAX_T, variables::t);
    inf.readEoln();
 
    int sum_n = 0;
 
    for (int testCase = 1; testCase <= t; testCase++) {
        setTestCase(testCase);
 
        int n = inf.readInt(limits::MIN_N, limits::MAX_N, variables::n);
        inf.readEoln();
        sum_n += n;
        ensuref(sum_n <= limits::MAX_SUM_N, "The sum of n over all test cases must not exceed %d", limits::MAX_SUM_N);
        inf.readInts(n, limits::MIN_A, limits::MAX_A, variables::a);
        inf.readEoln();
    }
    inf.readEof();
    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int max_ai = 5;
    int n = limits::MIN_N;
    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-max_ai")) {
            max_ai = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-n")) {
            n = atoi(argv[++i]);
            continue;
        }
    }

    vector<vector<int>> arrays;
    vector<int> current_array(n, 1);
    while (true) {
        arrays.emplace_back(current_array);

        current_array[n-1]++;
        int ptr = n - 1;
        while (ptr > 0) {
            if (current_array[ptr] <= max_ai) break;
            current_array[ptr-1]++;
            current_array[ptr] = 1;
            ptr--;
        }

        if (ptr == 0 && current_array[0] > max_ai) break;
    }

    cout << arrays.size() << endl;
    for (auto &array: arrays) {
        cout << array.size() << endl;
        println(array);
    }

    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int min_n  = limits::MIN_N;
    int max_n  = limits::MAX_N;
    int min_ai = limits::MIN_A;
    int max_ai = limits::MAX_A;

    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-min_n")) {
            min_n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_n")) {
            max_n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-min_ai")) {
            min_ai = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_ai")) {
            max_ai = atoi(argv[++i]);
            continue;
        }
    }

    int t = min(limits::MAX_T, limits::MAX_SUM_N / max_n);
    cout << t << endl;
    for (int _ = 0; _ < t; _++) {
        int n = rnd.next(min_n, max_n);
        cout << n << endl;
        for (int i = 0; i < n; i++) {
            cout << rnd.next(min_ai, max_ai);
            if (i < n - 1) cout << " ";
            else cout << endl;
        }
    }

    return 0;
}

#include <iostream>
#include <cassert>
#include "thresholds.cpp"
#include "testlib.h"

using namespace std;

vector<int> fibonacci {1, 1};
int freq[] = {
    -1, -1, -1, 300, 300, 300, 300, 300, 300, 300,
    300, 300, 300, 300, 300, 300, 300, 300, 300, 300,
    300, 300, 300, 300, 300, 300, 300, 300, 300, 300,
    300, 300, 300, 300, 100, 100, 100, 50, 50, 50,
    50, 50, 50, 50, 50
};

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int m = 2;
    while (fibonacci[m-2] + fibonacci[m-1] <= limits::MAX_A) {
        fibonacci.emplace_back(fibonacci[m-2] + fibonacci[m-1]);
        m++;
    }

    vector<vector<int>> arrays;
    for (int n = 3; n < 45; n++) {
        vector<int> array;
        for (int _ = 0; _ < freq[n]; _++) {
            array.emplace_back(fibonacci[rnd.next(0, m-1)]);
        }
        arrays.emplace_back(array);
    }

    cout << arrays.size() << endl;
    for (auto &array: arrays) {
        cout << array.size() << endl;
        println(array);
    }

    return 0;
}

#include <iostream>
#include <cassert>
#include "thresholds.cpp"
#include "testlib.h"

using namespace std;

vector<int> fibonacci {1, 1};

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int m = 2;
    while (fibonacci[m-2] + fibonacci[m-1] <= limits::MAX_A) {
        fibonacci.emplace_back(fibonacci[m-2] + fibonacci[m-1]);
        m++;
    }

    vector<int> array;
    int n = limits::MAX_N;
    
    for (int i = 0; i < m-2; i++) {
        array.emplace_back(fibonacci[i+1]);
    }
    
    for (int i = m-2; i < n; i++) {
        array.emplace_back(fibonacci.back());
    }

    cout << 1 << endl;
    cout << array.size() << endl;
    println(array);

    return 0;
}

Aside from a certain one, all generators work with this paradigm: generate a regular array of tentacle/path sizes, then convert it into the format used in this problem.

For some obscure generators:

• generator_tentacle_specified: Specify the range of the number of tentacles/paths for each Genokraken.
• generator_tentacle_weighted: Generate a Genokraken with exactly $$$\lfloor \frac{n-2}{2} \rfloor$$$ tentacles/paths, specify the number of tentacles/paths to be lengthened, and distribute the increasing path lengths with a certain weight (the higher the weight's absolute value, the more polarized the lengths are). Argument contain_first specify if the first tentacle/path (characterized by node $$$1$$$) is included in the chosen lengthening paths.

#include <cassert>
#include <set>
#include <vector>

namespace genokraken {
    inline int query_limit(int n) {
        return n * 2 - 6;
    }
    
    std::vector<int> generate_parent_list(std::vector<int> &tentacle_sizes) {
        assert(tentacle_sizes.size() > 0);
        assert(tentacle_sizes[0] > 1);
        assert(*min_element(tentacle_sizes.begin(), tentacle_sizes.end()) > 0);
        
        int n = 0;
        for (auto &x: tentacle_sizes) n += x;
        std::vector<int> p(n, 0);
        std::vector<int> last_node(tentacle_sizes.size(), 0);
        std::set<int> active_indices;
        for (int i=0; i<tentacle_sizes.size(); i++) active_indices.insert(i);
        
        int pointer = 1;
        std::set<int> cache;
        while (active_indices.size()) {
            for (auto i: active_indices) {
                p[pointer-1] = last_node[i];
                last_node[i] = pointer;
                
                tentacle_sizes[i]--;
                if (!tentacle_sizes[i]) cache.insert(i);
                pointer++;
            }
            
            while (cache.size()) {
                active_indices.erase(*cache.begin());
                cache.erase(cache.begin());
            }
        }
        
        return p;
    }
}

namespace variables {
    const char* t = "t";
    const char* n = "n";
    const char* p_i = "p_i";
}

namespace limits {
    const int MIN_T = 1;
    const int MAX_T = 500;

    const int MIN_N = 4;
    const int MAX_N = 10'000;

    const int MAX_SUM_N = 10'000;
}

#include <iostream>
#include "thresholds.cpp"
#include "testlib.h"
using namespace std;
 
int main(int argc, char *argv[]) {
    registerValidation(argc, argv);
    int t = inf.readInt(limits::MIN_T, limits::MAX_T, variables::t);
    inf.readEoln();
 
    int sum_n = 0;
 
    for (int testCase = 1; testCase <= t; testCase++) {
        setTestCase(testCase);
 
        int n = inf.readInt(limits::MIN_N, limits::MAX_N, variables::n);
        sum_n += n;
        ensuref(sum_n <= limits::MAX_SUM_N, "The sum of n over all test cases must not exceed %d", limits::MAX_SUM_N);
        inf.readEoln();
        
        vector<int> cnt(n, 0);
        vector<int> p = inf.readInts(n - 1, 0, n - 2, "p");
        for (int i = 0; i < n - 1; i++) {
            ensuref(p[i] <= i, "p[i] < i must hold");
            ensuref(i == 0 || p[i] >= p[i - 1], "p[i] <= p[i + 1] must hold");
            
            cnt[p[i]]++;
        }
        inf.readEoln();
        
        ensuref(cnt[1] == 1, "Node 1 must have exactly two other nodes connecting to it, but got %d here", cnt[1] + 1);
        for (int i = 2; i < n; i++) {
            ensuref(cnt[i] <= 1, "One of the parts after deleting node 0 is not a path");
        }
    }
    inf.readEof();
    return 0;
}

#include "testlib.h"
#include "thresholds.cpp"
#include <iostream>
using namespace std;

vector<int> p;

void readAns(InStream &in) {
    int n = p.size() + 1;
    vector<int> curp = in.readInts(n - 1, 0, n - 2, "p");
    if (p != curp) {
        in.quitf(_wa, "Incorrect genokraken structure");
    }
}

int main(int argc, char *argv[]) {
    registerTestlibCmd(argc, argv);

    int t = inf.readInt(limits::MIN_T, limits::MAX_T, variables::t);

    for (int testCase = 1; testCase <= t; testCase++) {
        setTestCase(testCase);
        int n = inf.readInt(limits::MIN_N, limits::MAX_N, variables::n);

        p = inf.readInts(n - 1, 0, n - 2, "p");
        readAns(ouf);
        readAns(ans);
    }

    quitf(_ok, "Passed, genokraken analyzed for %d test cases.", t);
    return 0;
}

#include <iostream>
#include "thresholds.cpp"
#include "genokraken.cpp"
#include "testlib.h"
using namespace std;

void send(int w) {cout << w << endl; cout.flush();}

int main(int argc, char* argv[]) {
    registerInteraction(argc, argv);

    int t = inf.readInt();
    cout << t << endl;
    cout.flush();
    
    for (int testCase=1; testCase<=t; testCase++) {
        setTestCase(testCase);

        int n = inf.readInt();

        vector<int> p(n, 0);
        int tentacle_count = 0;
        vector<int> tentacle_ids(n, -1);
    
        for (int i=1; i<n; i++) {
            p[i] = inf.readInt();
            if (p[i] == 0) {
                tentacle_ids[i] = tentacle_count;
                tentacle_count++;
            }
            else {
                tentacle_ids[i] = tentacle_ids[p[i]];
            }
        }
        
        cout << n << endl;
        cout.flush();
    
        int queries = 0, limit = genokraken::query_limit(n);
    
        while (true)
        {
            string cmd = ouf.readToken("[!?]{1,1}");

            if (cmd == "!") {
                for (int i=1; i<n; i++) {
                    int p_i = ouf.readInt();

                    tout << p_i;
                    if (i < n-1) tout << " ";
                    else tout << endl;
                }
                break;
            }
            
            if (cmd == "?") {
                int a = ouf.readInt();
                int b = ouf.readInt();
                
                if (a <= 0 || a >= n || b <= 0 || b >= n || a == b) {
                    send(-1);
                    quitf(_wa, "Invalid query!");
                    return 0;
                }
        
                queries++;
                
                if (queries > limit) {
                    send(-1);
                    quitf(_wa, "Query limit exceeded.");
                    return 0;
                }
                
                send(tentacle_ids[a] != tentacle_ids[b] ? 1 : 0);
                continue;
            }
            
            send(-1);
            quitf(_wa, "Invalid query!");
            return 0;
        }
    }
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "genokraken.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int min_n = limits::MIN_N;
    int max_n = limits::MIN_N;
    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-min_n")) {
            min_n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_n")) {
            max_n = atoi(argv[++i]);
            continue;
        }
    }

    set<vector<int>> distinct_arrays;
    vector<vector<int>> arrays;
    set<vector<int>> templates, cache;
    templates.insert(vector<int> {2});
    for (int n=3; n<=max_n; n++) {
        
        if (n >= min_n) {
            for (auto &arr: templates) {
                if (distinct_arrays.find(arr) == distinct_arrays.end()) {
                    distinct_arrays.insert(arr);
                    arrays.emplace_back(arr);
                }
            }
        }

        for (auto &arr: templates) {
            for (int i=arr.size(); i>=0; i--) {
                vector<int> copy = arr;
                if (i < arr.size()) copy[i]++;
                else copy.emplace_back(1);
                
                cache.insert(copy);
            }
        }
        
        templates.clear();
        for (auto &arr: cache) templates.insert(arr);
        cache.clear();
    }

    cout << arrays.size() << endl;
    for (auto &array: arrays) {
        vector<int> p = genokraken::generate_parent_list(array);
        cout << p.size() + 1 << endl;
        println(p);
    }

    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "genokraken.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int min_n  = limits::MIN_N;
    int max_n  = limits::MAX_N;

    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-min_n")) {
            min_n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_n")) {
            max_n = atoi(argv[++i]);
            continue;
        }
    }

    int t = min(limits::MAX_T, limits::MAX_SUM_N / max_n);
    cout << t << endl;
    for (int _ = 0; _ < t; _++) {
        int n = rnd.next(min_n, max_n);
        
        int tentacle_count = rnd.next(1, n - 2);
        
        vector<int> tentacle_sizes(tentacle_count, 1);
        tentacle_sizes[0]++;
        for (int i = 1 + tentacle_count + 1; i < n; i++) {
            int tentacle_index = rnd.next(0, tentacle_count - 1);
            tentacle_sizes[tentacle_index]++;
        }
        
        vector<int> p = genokraken::generate_parent_list(tentacle_sizes);
        cout << p.size() + 1 << endl;
        println(p);
    }

    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "genokraken.cpp"
#include "testlib.h"
 
using namespace std;
 
int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
 
    int n = limits::MAX_N;
 
    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-n")) {
            n = atoi(argv[++i]);
            continue;
        }
    }
 
    int t = min(limits::MAX_T, limits::MAX_SUM_N / n);
    cout << t << endl;
    for (int _ = 0; _ < t; _++) {
        vector<int> p(n - 1);
        for (int i = 0; i < n - 1; i++) p[i] = i;
        cout << p.size() + 1 << endl;
        println(p);
    }
 
    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "genokraken.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int n        = limits::MAX_N;
    int min_ten  = limits::MIN_N;
    int max_ten  = limits::MAX_N;

    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-n")) {
            n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-min_ten")) {
            min_ten = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-max_ten")) {
            max_ten = atoi(argv[++i]);
            continue;
        }
    }

    int t = min(limits::MAX_T, limits::MAX_SUM_N / n);
    cout << t << endl;
    for (int _ = 0; _ < t; _++) {
        int tentacle_count = rnd.next(max(1, min_ten), min(n-2, max_ten));
        
        vector<int> tentacle_sizes(tentacle_count, 1);
        tentacle_sizes[0]++;
        for (int i = 1 + tentacle_count + 1; i < n; i++) {
            int tentacle_index = rnd.next(0, tentacle_count - 1);
            tentacle_sizes[tentacle_index]++;
        }
        
        vector<int> p = genokraken::generate_parent_list(tentacle_sizes);
        cout << p.size() + 1 << endl;
        println(p);
    }

    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "genokraken.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int n              = limits::MAX_N;
    int tentacle_chosen = limits::MAX_N;
    int random_weight  = 0;
    int contain_first  = 0;

    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-n")) {
            n = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-contain_first")) {
            contain_first = 1;
            continue;
        }
        if (!strcmp(argv[i], "-tentacle_chosen")) {
            tentacle_chosen = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-random_weight")) {
            random_weight = atoi(argv[++i]);
            continue;
        }
    }

    int t = min(limits::MAX_T, limits::MAX_SUM_N / n);
    cout << t << endl;
    for (int _ = 0; _ < t; _++) {
        int tentacle_count = (n - 2) / 2;
        vector<int> tentacle_sizes(tentacle_count, 1);
        tentacle_sizes[0]++;

        vector<int> tentacle_chosen_indices;
        for (int i = 1; i < tentacle_count; i++) tentacle_chosen_indices.emplace_back(i);
        shuffle(tentacle_chosen_indices.begin(), tentacle_chosen_indices.end());
        while (tentacle_chosen_indices.size() + contain_first > tentacle_chosen) tentacle_chosen_indices.pop_back();
        if (contain_first) tentacle_chosen_indices.emplace_back(0);
        
        for (int i = 1 + tentacle_count + 1; i < n; i++) {
            int tentacle_index = tentacle_chosen_indices[rnd.wnext(0, tentacle_chosen - 1, random_weight)];
            tentacle_sizes[tentacle_index]++;
        }
        
        vector<int> p = genokraken::generate_parent_list(tentacle_sizes);
        cout << p.size() + 1 << endl;
        println(p);
    }

    return 0;
}

Nothing much. Just crafting basic things and helping MofK on the hassle work.

namespace variables {
    const char* t = "t";
    const char* n = "n";
    const char* a_i = "a_i";
}

namespace limits {
    const int MIN_T = 1;
    const int MAX_T = 10'000;

    const int MIN_N = 1;
    const int MAX_N = 1'000'000;
    const int MIN_A = 1;
    const int MAX_A = 1'000'000'000;

    const int MAX_SUM_N = 1'000'000;
}

#include "testlib.h"
#include<bits/stdc++.h>
using namespace std;

const int min_t = 1;
const int max_t = 10'000;
const int min_n = 1;
const int max_n = 1'000'000;
const int min_a = 1;
const int max_a = 1'000'000'000;

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);
    
    int t = inf.readInt(min_t, max_t, "t");
    inf.readEoln();
    
    int sum_n = 0;
    for (int i = 0; i < t; ++i) {
        setTestCase(i + 1);
        int n = inf.readInt(min_n, max_n, "n");
        inf.readEoln();
        sum_n += n;
        ensuref(sum_n <= max_n, "The sum of n over all test cases exceeds %d", max_n);
        vector<int> a = inf.readInts(n, min_a, max_a, "a");
        inf.readEoln();
    }

    inf.readEof();
    return 0;
}

#include <iostream>
#include <vector>
#include "thresholds.cpp"
#include "testlib.h"

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);

    int max_ai = 5;
    int n = limits::MIN_N;
    for (int i = 1; i < argc; i++) {
        if (!strcmp(argv[i], "-max_ai")) {
            max_ai = atoi(argv[++i]);
            continue;
        }
        if (!strcmp(argv[i], "-n")) {
            n = atoi(argv[++i]);
            continue;
        }
    }

    vector<vector<int>> arrays;
    
    if (n == 3) {
        for (int x = 1; x <= max_ai; x++) arrays.push_back(vector<int>(1, x));
        for (int x = 1; x <= max_ai; x++) {
            for (int y = 1; y <= max_ai; y++) arrays.push_back(vector<int>{x, y});
        }
    }
    
    vector<int> current_array(n, 1);
    while (true) {
        arrays.emplace_back(current_array);

        current_array[n-1]++;
        int ptr = n - 1;
        while (ptr > 0) {
            if (current_array[ptr] <= max_ai) break;
            current_array[ptr-1]++;
            current_array[ptr] = 1;
            ptr--;
        }

        if (ptr == 0 && current_array[0] > max_ai) break;
    }

    cout << arrays.size() << endl;
    for (auto &array: arrays) {
        cout << array.size() << endl;
        println(array);
    }

    return 0;
}