#include "richest.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;

//vector<ll> W;
//ll ct = 0, cs = 0;
//vector<ll> ask(vector<ll> a, vector<ll> b) {
//    assert(a.size() == b.size());
//    ct++;
//    cs += (ll)a.size();
//
//    vector<ll> c(a.size());
//    for (ll i = 0; i < a.size(); i++) {
//        if (a[i] == b[i])
//            assert(a[i] != b[i]);
//        if (W[a[i]] > W[b[i]])
//            c[i] = a[i];
//        else
//            c[i] = b[i];
//    }
//    return c;
//}

ll on2(ll n) {
    vector<ll> a, b;
    for (ll i = 1; i < n; i++) {
        for (ll j = 0; j < i; j++) {
            a.push_back(i);
            b.push_back(j);
        }
    }

    vector<ll> c = ask(a, b);
    std::reverse(c.begin(), c.end());

    vector<vector<bool>> cmp(n, vector<bool>(n, true));
    for (ll i = 1; i < n; i++)
        for (ll j = 0; j < i; j++) {
            cmp[i][j] = c.back() == i;
            cmp[j][i] = c.back() == j;
            c.pop_back();
        }

    for (ll i = 0; i < n; i++) {
        bool good = true;
        for (ll j = 0; j < n; j++)
            good = good and cmp[i][j];

        if (good)
            return i;
    }
    return 0;
}

vector<ll> ds = {500'000, 250'000, 125'000, 62'500, 20'833, 3472, 183, 1};

ll on(ll n) {
    vector<ll> p(n);
    std::iota(p.begin(), p.end(), 0);

    for (ll d : ds) {
        ll a = d - n % d;
        ll b = n % d;
        ll fl = n / d;
        ll ce = (n + d - 1) / d;

        vector<ll> iv, jv;

        ll s = 0;
        for (ll i = 0; i < a; i++) {
            for (ll j = s + 1; j < s + fl; j++)
                for (ll k = s; k < j; k++) {
                    iv.push_back(p[j]);
                    jv.push_back(p[k]);
                }
            s += fl;
        }
        for (ll i = 0; i < b; i++) {
            for (ll j = s + 1; j < s + ce; j++)
                for (ll k = s; k < j; k++) {
                    iv.push_back(p[j]);
                    jv.push_back(p[k]);
                }
            s += ce;
        }

        iv = ask(iv, jv);
        std::reverse(iv.begin(), iv.end());

        s = 0;
        p.clear();
        for (ll i = 0; i < a; i++) {
            vector<vector<bool>> cm(fl, vector<bool>(fl, true));
            for (ll j = s + 1; j < s + fl; j++)
                for (ll k = s; k < j; k++) {
                    cm[j - s][k - s] = iv.back() == p[j];
                    cm[k - s][j - s] = iv.back() == p[k];
                    iv.pop_back();
                }

            for (ll j = 0; j < fl; j++) {
                bool good = true;
                for (ll k = 0; k < fl; k++)
                    good = good and cm[j][k];

                if (good)
                    p.push_back(p[j + s]);
            }

            s += fl;
        }

        for (ll i = 0; i < b; i++) {
            vector<vector<bool>> cm(ce, vector<bool>(ce, true));
            for (ll j = s + 1; j < s + ce; j++)
                for (ll k = s; k < j; k++) {
                    cm[j - s][k - s] = iv.back() == p[j];
                    cm[k - s][j - s] = iv.back() == p[k];
                    iv.pop_back();
                }

            for (ll j = 0; j < ce; j++) {
                bool good = true;
                for (ll k = 0; k < ce; k++)
                    good = good and cm[j][k];

                if (good)
                    p.push_back(p[j + s]);
            }

            s += ce;
        }
        n = (ll)p.size();
    }

    return p[0];
}

ll richest(ll N, ll T, ll S) {
    if (T == 1)
        return on2(N);
    return on(N);
}

//ll main() {
//    random_device rd;
//    mt19937 rng(rd());
//
//    ll mt = 0, ms = 0;
//    ll t = 5;
//    while (t--) {
//        ll N = 1'000'000, T = 20, S = 2'000'000;
//        W.resize(N);
//        std::iota(W.begin(), W.end(), 0);
//        shuffle(W.begin(), W.end(), rng);
//
//        ct = 0, cs = 0;
//        richest(N, T, S);
//        cout << ct << " " << cs << "\n";
//        ms = max(ms, cs);
//        mt = max(mt, ct);
//    }
//
//    cout << "\n\n" << mt << " " << ms << "\n";
//
//    return 0;
//
//}

//int main() {
//    ll T = 5, N = 62'500, INF = 1e12;
//    vector<vector<ll>> dp(T + 1, vector<ll>(N + 1, INF));
//    vector<vector<ll>> pr(T + 1, vector<ll>(N + 1, -1));
//    dp[0][N] = 937'500;
//    for (ll t = 0; t < T; t++) {
//        cout << t << "\n";
//        for (ll i = 2; i <= N; i++) {
//            for (ll d = 1; d <= i / 2; d++) {
//                ll a = d - i % d;
//                ll b = i % d;
//                ll fl = i / d;
//                fl = fl * (fl - 1) / 2;
//                ll ce = (i + d - 1) / d;
//                ce = ce * (ce - 1) / 2;
//                if (a *fl + b *ce < 0)
//                    cout << "chuj\n";
//
//                if (dp[t][i] + a * fl + b * ce < dp[t + 1][d]) {
//                    dp[t + 1][d] = dp[t][i] + a * fl + b * ce;
//                    pr[t + 1][d] = d * INF + i;
//                }
//            }
//        }
//        cout << dp[t + 1][1] << "\n";
//    }
//
//
//    return 0;
//}