gen_perf.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// Proper random function (no modulo bias)
ll get(ll l, ll r)
{
    return uniform_int_distribution<ll>(l, r)(rng);
}

// Random string
string getString(int n, bool lowercase_only = true)
{
    string s(n, 'a');
    for (int i = 0; i < n; i++)
    {
        s[i] = char('a' + get(0, 25));
        if (!lowercase_only && get(0, 1))
        {
            s[i] = char('A' + (s[i] - 'a'));
        }
    }
    return s;
}

// Random array
template <typename T> vector<T> getArray(int n, T l, T r)
{
    vector<T> v(n);
    for (int i = 0; i < n; i++)
    {
        v[i] = get(l, r);
    }
    return v;
}

// Random permutation (1-indexed values 1..n)
vector<int> getPermutation(int n)
{
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    shuffle(p.begin(), p.end(), rng);
    return p;
}

// Random tree (1-indexed)
vector<pair<int, int>> getTree(int n)
{
    vector<pair<int, int>> edges;
    for (int i = 2; i <= n; i++)
    {
        int p = get(1, i - 1);
        edges.push_back({p, i});
    }
    shuffle(edges.begin(), edges.end(), rng);
    return edges;
}

// Random simple graph (safe: asserts m is feasible)
vector<pair<int, int>> getGraph(int n, int m)
{
    ll max_edges = (ll) n * (n - 1) / 2;
    assert(m <= max_edges && "get_graph: m exceeds maximum possible edges for n nodes");

    set<pair<int, int>> s;
    while ((int) s.size() < m)
    {
        int u = get(1, n);
        int v = get(1, n);
        if (u == v)
            continue;
        if (u > v)
            swap(u, v); // normalise to avoid both (u,v) and (v,u) checks
        s.insert({u, v});
    }
    vector<pair<int, int>> edges(s.begin(), s.end());
    shuffle(edges.begin(), edges.end(), rng);
    return edges;
}

// ============================================================
// ✏️  EDIT THIS PER PROBLEM
//
// Rules for gen_perf:
//   - Always emit WORST-CASE inputs, not random ones
//   - Think about what input structure maximises your
//     algorithm's work, not just what maximises n or t
//
// Common adversarial patterns:
//   - O(n^2) algorithm      → t=1, n=N_MAX
//   - Per-test setup cost   → t=T_MAX, n=1, val=VAL_MAX
//   - DFS/backtracking      → inputs that maximise branching
//   - Sorting-based         → reverse sorted input
//
// Sum constraints (e.g. sum of n <= 5000):
//   - Test BOTH extremes:
//       t=T_MAX, n=1  (many tiny test cases)
//       t=1, n=N_SUM  (one large test case)
//   - Run perf_test.bat separately for each by editing here
// ============================================================
void make_test()
{
    // Example: t=T_MAX, n=1, val=VAL_MAX
    // (edit to match your problem's worst case)
    cout << 1 << "\n";
    cout << 5000 << "\n";
}

int main(int argc, char* argv[])
{
    if (argc > 1)
        rng.seed(atoll(argv[1]));

    // ✏️  Set t to match your adversarial scenario
    int t = 5000;
    cout << t << "\n";
    while (t--)
        make_test();
}