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

• 問題: No.1743 Permutation Code
• ユーザー: harurun
• 提出日時: 2026-07-09 04:28:16
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 4,817 bytes
• コンパイル時間: 1,286 ms
• コンパイル使用メモリ: 228,364 KB
• 実行使用メモリ: 247,212 KB
• 最終ジャッジ日時: 2026-07-09 04:28:23
• 合計ジャッジ時間: 6,619 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	WA * 30

ソースコード

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

string C;
int L, N, M;

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

    for (long long len = 1, l = 1; l <= n; len++) {
        long long 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((unsigned)x);
}

struct Edge {
    int from;
    int to;
    int value;
    int len;
    bool alive = true;
};

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_length(N);

    vector<Edge> edges;
    vector<vector<int>> out(L + 1);
    vector<vector<int>> byValue(N + 1);

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

        int 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 t = s + len;

            if (t < L && C[t] != '1') continue;

            int id = (int)edges.size();
            edges.push_back({s, t, v, len, true});
            out[s].push_back(id);
            byValue[v].push_back(id);
        }
    }

    vector<int> chosenFrom(L + 1, -1);
    vector<int> chosenValue(N + 1, -1);
    vector<int> aliveOut(L + 1, 0);
    vector<int> aliveValue(N + 1, 0);

    for (int i = 0; i <= L; i++) {
        aliveOut[i] = (int)out[i].size();
    }

    for (int v = 1; v <= N; v++) {
        aliveValue[v] = (int)byValue[v].size();
    }

    queue<pair<int, int>> q;

    auto push_pos = [&](int p) {
        if (p < L && chosenFrom[p] == -1 && aliveOut[p] == 1) {
            q.push({0, p});
        }
    };

    auto push_val = [&](int v) {
        if (chosenValue[v] == -1 && aliveValue[v] == 1) {
            q.push({1, v});
        }
    };

    auto erase_edge = [&](int id) {
        if (!edges[id].alive) return;

        edges[id].alive = false;

        int s = edges[id].from;
        int v = edges[id].value;

        aliveOut[s]--;
        aliveValue[v]--;

        push_pos(s);
        push_val(v);
    };

    auto choose_edge = [&](int id) {
        if (!edges[id].alive) return;

        int s = edges[id].from;
        int t = edges[id].to;
        int v = edges[id].value;

        chosenFrom[s] = id;
        chosenValue[v] = id;

        for (int x : out[s]) {
            if (x != id) erase_edge(x);
        }

        for (int x : byValue[v]) {
            if (x != id) erase_edge(x);
        }

        // この辺を選んだら、区間内部からは開始できない
        for (int p = s + 1; p < t; p++) {
            for (int x : out[p]) {
                erase_edge(x);
            }
        }

        push_pos(t);
    };

    push_pos(0);

    for (int v = 1; v <= N; v++) {
        push_val(v);
    }

    while (!q.empty()) {
        auto [type, x] = q.front();
        q.pop();

        if (type == 0) {
            int p = x;

            if (p >= L || chosenFrom[p] != -1 || aliveOut[p] != 1) continue;

            int id = -1;

            for (int e : out[p]) {
                if (edges[e].alive) {
                    id = e;
                    break;
                }
            }

            if (id != -1) {
                choose_edge(id);
            }
        } else {
            int v = x;

            if (chosenValue[v] != -1 || aliveValue[v] != 1) continue;

            int id = -1;

            for (int e : byValue[v]) {
                if (edges[e].alive) {
                    id = e;
                    break;
                }
            }

            if (id != -1) {
                choose_edge(id);
            }
        }
    }

    vector<int> ans;

    int pos = 0;

    while (pos < L) {
        int id = chosenFrom[pos];

        if (id == -1) {
            /*
                ここに来る場合、まだ複数候補が残っている。
                つまり、この入力では多項式時間の一意確定だけでは足りない。

                正確に解くには、ここから局所探索が必要。
                ただし全体 DFS ではなく、この未確定区間だけに限定する。
            */
            return 0;
        }

        ans.push_back(edges[id].value);
        pos = edges[id].to;
    }

    if ((int)ans.size() != N) {
        return 0;
    }

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

    cout << '\n';

    return 0;
}