Submission #1195322

---

Source Code Expand

#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 201;
i64 LIM = 1e13;
i64 dp[maxn][maxn];

i64 common_sub(vi s, vi t) {
    int n = s.size(), m = t.size();
    forn(i, n + 1) forn(j, m + 1) dp[i][j] = 0;
    dp[0][0] = 1;
    forn(i, n + 1) forn(j, m + 1) {
        if (i) dp[i][j] += dp[i - 1][j];
        if (j) dp[i][j] += dp[i][j - 1];
        if (i && j && s[i - 1] != t[j - 1]) dp[i][j] -= dp[i - 1][j - 1];
        if (dp[i][j] >= LIM) return LIM;
    }
    return dp[n][m];
}

int main() {
    i64 n;
    cin >> n;
/*    if (n == 1) {
        cout << "1\n1\n";
        return 0;
    }*/
    vi a;
    i64 ans = 0;
    int x = 1;
    while (ans < n) {
        int bi = -1;
        i64 bx = -1e9;
        forn(i, a.size() + 1) {
            i64 res = common_sub(vi(a.begin(), a.begin() + i), vi(a.begin() + i, a.end()));
            if (ans + res <= n && res > bx) bx = res, bi = i;
//            cerr << i << ' ' << res << '\n';
        }

        vi b;
        forn(i, a.size() + 1) {
            if (!i) b.pb(x);
            if (i == bi) b.pb(x);
            if (i < a.size()) b.pb(a[i]);
        }
        a = b;
        ans += bx;
        ++x;
    }
    cout << a.size() << '\n';
    forn(i, a.size()) cout << a[i] << " \n"[i + 1 == a.size()];
}

Submission Info

Judge Result