#1170605 (C++17) No.1743 Permutation Code

• 問題: No.1743 Permutation Code
• ユーザー: harurun
• 提出日時: 2026-07-09 04:20:12
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: MLE
• 実行時間: -
• コード長: 2,912 bytes
• コンパイル時間: 1,485 ms
• コンパイル使用メモリ: 232,996 KB
• 実行使用メモリ: 1,176,800 KB
• 最終ジャッジ日時: 2026-07-09 04:20:29
• 合計ジャッジ時間: 12,224 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 7 MLE * 1 -- * 22

ソースコード

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

using ull = unsigned long long;

string C;
int L, N, M;

vector<vector<pair<int, int>>> cand;
vector<int> bitLen;

unordered_map<ull, char> memo;
unordered_map<ull, int> choice;

ull fullMask;

long long total_len(long long n) {
    long long res = 0;

    for (long long len = 1, l = 1; l <= n; len++) {
        long long r;

        if (l > LLONG_MAX / 2) r = n;
        else r = min(n, l * 2 - 1);

        res += len * (r - l + 1);

        if (l > n / 2) break;
        l <<= 1;
    }

    return res;
}

int bit_length(int x) {
    return 32 - __builtin_clz(x);
}

bool dfs(ull mask, int pos) {
    if (mask == fullMask) {
        return pos == L;
    }

    if (pos >= L) return false;
    if (C[pos] != '1') return false;

    auto it = memo.find(mask);
    if (it != memo.end()) {
        return it->second;
    }

    for (auto [v, len] : cand[pos]) {
        ull bit = 1ULL << (v - 1);

        if (mask & bit) continue;

        ull nmask = mask | bit;

        if (dfs(nmask, pos + len)) {
            memo[mask] = 1;
            choice[mask] = v;
            return true;
        }
    }

    memo[mask] = 0;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> C;
    L = (int)C.size();

    long long lo = 1, hi = 1;

    while (total_len(hi) < L) {
        hi <<= 1;
    }

    while (lo < hi) {
        long long mid = (lo + hi) / 2;

        if (total_len(mid) >= L) hi = mid;
        else lo = mid + 1;
    }

    if (total_len(lo) != L) {
        return 0;
    }

    N = (int)lo;

    /*
        この DP は used 集合を bitmask で持つため、
        N <= 63 を仮定する。
        N がこれより大きい制約なら、別の問題固有の性質が必要。
    */
    if (N > 63) {
        return 0;
    }

    M = bit_length(N);

    fullMask = (1ULL << N) - 1;

    bitLen.assign(N + 1, 0);
    for (int v = 1; v <= N; v++) {
        bitLen[v] = bit_length(v);
    }

    cand.assign(L + 1, {});

    for (int pos = 0; pos < L; pos++) {
        if (C[pos] != '1') continue;

        int v = 0;

        for (int len = 1; len <= M && pos + len <= L; len++) {
            v = (v << 1) + (C[pos + len - 1] - '0');

            if (v > N) break;

            int nxt = pos + len;

            if (nxt == L || C[nxt] == '1') {
                cand[pos].push_back({v, len});
            }
        }
    }

    memo.reserve(1 << min(N, 20));
    choice.reserve(1 << min(N, 20));

    if (!dfs(0, 0)) {
        return 0;
    }

    vector<int> ans;

    ull mask = 0;
    int pos = 0;

    while (mask != fullMask) {
        int v = choice[mask];

        ans.push_back(v);

        mask |= 1ULL << (v - 1);
        pos += bitLen[v];
    }

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }

    cout << '\n';

    return 0;
}