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

• 問題: No.1743 Permutation Code
• ユーザー: harurun
• 提出日時: 2026-07-09 04:15:00
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,338 bytes
• コンパイル時間: 1,654 ms
• コンパイル使用メモリ: 225,996 KB
• 実行使用メモリ: 5,632 KB
• 最終ジャッジ日時: 2026-07-09 04:15:27
• 合計ジャッジ時間: 12,146 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

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

ソースコード

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

const int INF = 1e9;

string C;
int L, N, M;

vector<int> ans;
vector<int> remLen;
vector<int> lastPos;
vector<int> oneSuf;
vector<unsigned char> used;

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 - 1) / 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_len(long long x) {
    return 64 - __builtin_clzll(x);
}

struct SegTree {
    int n;
    vector<int> seg;

    void init(const vector<int>& a) {
        int sz = (int)a.size() - 1;
        n = 1;
        while (n < sz) n <<= 1;

        seg.assign(2 * n, INF);

        for (int i = 1; i <= sz; i++) {
            seg[n + i - 1] = a[i];
        }

        for (int i = n - 1; i >= 1; i--) {
            seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
        }
    }

    void set_val(int idx, int val) {
        int p = n + idx - 1;
        seg[p] = val;

        while (p >>= 1) {
            seg[p] = min(seg[p << 1], seg[p << 1 | 1]);
        }
    }

    int min_all() const {
        return seg[1];
    }
};

SegTree st;

int candidate_count(int pos) {
    if (pos == L) return 1;
    if (C[pos] != '1') return 0;

    int cnt = 0;
    long long v = 0;

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

        if (v > N) break;
        if (remLen[len] == 0) continue;

        int nxt = pos + len;

        if (nxt < L && C[nxt] != '1') continue;
        if (used[(int)v]) continue;

        cnt++;
    }

    return cnt;
}

struct Cand {
    int score;
    int slack;
    int len;
    int v;
};

bool dfs(int pos, int remain) {
    if (pos == L) {
        return remain == 0;
    }

    if (remain == 0) return false;
    if (C[pos] != '1') return false;

    if (oneSuf[pos] < remain) return false;

    // まだ使っていない値のうち、最後の開始位置を過ぎたものがあれば不可能
    if (st.min_all() < pos) return false;

    vector<Cand> cand;
    long long v = 0;

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

        if (v > N) break;
        if (remLen[len] == 0) continue;

        int x = (int)v;
        int nxt = pos + len;

        if (nxt < L && C[nxt] != '1') continue;
        if (used[x]) continue;

        if (nxt == L && remain != 1) continue;
        if (nxt < L && oneSuf[nxt] < remain - 1) continue;

        used[x] = 1;
        remLen[len]--;
        st.set_val(x, INF);

        bool ok = true;

        // この値を選んだ結果、他の値の最後の開始位置を飛び越えるなら不可
        int mn = st.min_all();
        if (mn < nxt) ok = false;

        int score = 0;
        if (ok && nxt < L) {
            score = candidate_count(nxt);
            if (score == 0) ok = false;
        }

        if (ok) {
            int slack = (mn >= INF ? INF : mn - nxt);
            cand.push_back({score, slack, len, x});
        }

        st.set_val(x, lastPos[x]);
        remLen[len]++;
        used[x] = 0;
    }

    sort(cand.begin(), cand.end(), [](const Cand& a, const Cand& b) {
        if (a.score != b.score) return a.score < b.score;
        if (a.slack != b.slack) return a.slack < b.slack;
        return a.len > b.len;
    });

    for (const auto& c : cand) {
        int nxt = pos + c.len;

        used[c.v] = 1;
        remLen[c.len]--;
        st.set_val(c.v, INF);
        ans.push_back(c.v);

        if (dfs(nxt, remain - 1)) return true;

        ans.pop_back();
        st.set_val(c.v, lastPos[c.v]);
        remLen[c.len]++;
        used[c.v] = 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;
    M = bit_len(N);

    remLen.assign(M + 1, 0);

    for (int len = 1; len < M; len++) {
        remLen[len] = (int)(1LL << (len - 1));
    }

    remLen[M] = (int)(N - (1LL << (M - 1)) + 1);

    used.assign(N + 1, 0);
    ans.reserve(N);

    oneSuf.assign(L + 1, 0);
    for (int i = L - 1; i >= 0; i--) {
        oneSuf[i] = oneSuf[i + 1] + (C[i] == '1');
    }

    lastPos.assign(N + 1, -1);

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

        long long v = 0;

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

            if (v > N) break;

            int e = s + len;

            if (e == L || C[e] == '1') {
                lastPos[(int)v] = s;
            }
        }
    }

    for (int v = 1; v <= N; v++) {
        if (lastPos[v] == -1) return 0;
    }

    vector<int> init(N + 1);
    for (int v = 1; v <= N; v++) {
        init[v] = lastPos[v];
    }

    st.init(init);

    dfs(0, N);

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

    return 0;
}