結果

問題 No.1743 Permutation Code
ユーザー harurun
提出日時 2026-07-09 05:47:14
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 8,086 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,581 ms
コンパイル使用メモリ 236,764 KB
実行使用メモリ 5,632 KB
最終ジャッジ日時 2026-07-09 05:47:36
合計ジャッジ時間 15,604 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    for (long long len = 1, l = 1; l <= n; len++, l <<= 1) {
        long long r = min(n, (1LL << len) - 1);
        res += len * (r - l + 1);

        if (l > n / 2) break;
    }

    return res;
}

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

struct RowInfo {
    int start;
    int len;
    int value;
};

struct DLX {
    int nCol;
    int primaryCols;

    vector<int> L, R, U, D;
    vector<int> col, row, sz;
    vector<int> answer;

    vector<RowInfo>* rowsInfo;

    long long nodes;
    long long nodeLimit;
    int branchLimit;

    mt19937 rng;
    chrono::steady_clock::time_point deadline;

    DLX(int nCol, int primaryCols, int reserveNodes, vector<RowInfo>* rowsInfo)
        : nCol(nCol), primaryCols(primaryCols), rowsInfo(rowsInfo) {

        int cap = nCol + 1 + reserveNodes;

        L.reserve(cap);
        R.reserve(cap);
        U.reserve(cap);
        D.reserve(cap);
        col.reserve(cap);
        row.reserve(cap);

        L.resize(nCol + 1);
        R.resize(nCol + 1);
        U.resize(nCol + 1);
        D.resize(nCol + 1);
        col.resize(nCol + 1);
        row.resize(nCol + 1, -1);
        sz.assign(nCol + 1, 0);

        // 1..primaryCols だけ root list に入れる。
        // primary: 文字位置
        // secondary: 値
        L[0] = primaryCols;
        R[0] = primaryCols == 0 ? 0 : 1;

        for (int i = 1; i <= primaryCols; i++) {
            L[i] = i - 1;
            R[i] = i == primaryCols ? 0 : i + 1;
        }

        for (int i = primaryCols + 1; i <= nCol; i++) {
            L[i] = R[i] = i;
        }

        for (int i = 0; i <= nCol; i++) {
            U[i] = D[i] = i;
            col[i] = i;
        }

        nodes = 0;
        nodeLimit = 0;
        branchLimit = 0;
    }

    void add_node(int r, int c, int& first) {
        int id = (int)col.size();

        L.push_back(id);
        R.push_back(id);
        U.push_back(U[c]);
        D.push_back(c);
        col.push_back(c);
        row.push_back(r);

        D[U[c]] = id;
        U[c] = id;
        sz[c]++;

        if (first == -1) {
            first = id;
            L[id] = R[id] = id;
        } else {
            R[id] = first;
            L[id] = L[first];
            R[L[first]] = id;
            L[first] = id;
        }
    }

    void add_row(int r, const vector<int>& cols) {
        int first = -1;

        for (int c : cols) {
            add_node(r, c, first);
        }
    }

    void cover(int c) {
        R[L[c]] = R[c];
        L[R[c]] = L[c];

        for (int i = D[c]; i != c; i = D[i]) {
            for (int j = R[i]; j != i; j = R[j]) {
                D[U[j]] = D[j];
                U[D[j]] = U[j];
                sz[col[j]]--;
            }
        }
    }

    void uncover(int c) {
        for (int i = U[c]; i != c; i = U[i]) {
            for (int j = L[i]; j != i; j = L[j]) {
                sz[col[j]]++;
                D[U[j]] = j;
                U[D[j]] = j;
            }
        }

        R[L[c]] = c;
        L[R[c]] = c;
    }

    bool time_over() const {
        return chrono::steady_clock::now() >= deadline;
    }

    long long row_score(int nodeId) {
        int rid = row[nodeId];
        const RowInfo& info = (*rowsInfo)[rid];

        int valueCol = primaryCols + info.value;

        long long valueDegree = sz[valueCol];
        long long positionDegreeSum = 0;

        for (int j = nodeId;; j = R[j]) {
            int c = col[j];

            if (c <= primaryCols) {
                positionDegreeSum += sz[c];
            }

            if (R[j] == nodeId) break;
        }

        return valueDegree * 1000000LL
             + positionDegreeSum * 1000LL
             + (long long)(rng() % 1000);
    }

    bool solve() {
        if (++nodes > nodeLimit) return false;

        if ((nodes & 4095) == 0 && time_over()) {
            return false;
        }

        if (R[0] == 0) {
            return true;
        }

        int c = R[0];

        for (int j = R[c]; j != 0; j = R[j]) {
            if (sz[j] < sz[c]) {
                c = j;
            }
        }

        if (sz[c] == 0) {
            return false;
        }

        vector<int> rows;
        rows.reserve(sz[c]);

        for (int i = D[c]; i != c; i = D[i]) {
            rows.push_back(i);
        }

        sort(rows.begin(), rows.end(), [&](int a, int b) {
            return row_score(a) < row_score(b);
        });

        int lim = branchLimit == 0 ? (int)rows.size()
                                   : min<int>(rows.size(), branchLimit);

        cover(c);

        for (int k = 0; k < lim; k++) {
            int i = rows[k];

            answer.push_back(row[i]);

            for (int j = R[i]; j != i; j = R[j]) {
                cover(col[j]);
            }

            if (solve()) {
                return true;
            }

            for (int j = L[i]; j != i; j = L[j]) {
                uncover(col[j]);
            }

            answer.pop_back();
        }

        uncover(c);
        return false;
    }
};

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

    string C;
    cin >> C;

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

    int lo = 1, hi = 65535;

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

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

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

    int N = lo;
    int M = bit_length(N);

    vector<RowInfo> rows;
    vector<vector<int>> rowCols;

    int reserveNodes = 0;

    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;

            vector<int> cols;
            cols.reserve(len + 1);

            // primary columns: 1..L
            // 文字位置をちょうど1回覆う。
            for (int p = s; p < t; p++) {
                cols.push_back(p + 1);
            }

            // secondary columns: L+1..L+N
            // 値を高々1回だけ使う。
            cols.push_back(L + v);

            rows.push_back({s, len, v});
            rowCols.push_back(move(cols));

            reserveNodes += len + 1;
        }
    }

    DLX dlx(L + N, L, reserveNodes, &rows);

    for (int i = 0; i < (int)rowCols.size(); i++) {
        dlx.add_row(i, rowCols[i]);
    }

    int attempts;
    int branchLimit;
    long long nodeLimit;
    int timeMs = 1900;

    if (N <= 100) {
        attempts = 1;
        branchLimit = 0;       // 小さい場合はほぼ正確に解く
        nodeLimit = 20000000;
    } else if (N <= 1000) {
        attempts = 6;
        branchLimit = 6;
        nodeLimit = 3000000;
    } else {
        attempts = 8;
        branchLimit = 3;
        nodeLimit = 1200000;
    }

    auto deadline = chrono::steady_clock::now() + chrono::milliseconds(timeMs);

    vector<int> answerIds;

    for (int a = 0; a < attempts; a++) {
        if (chrono::steady_clock::now() >= deadline) break;

        dlx.answer.clear();
        dlx.nodes = 0;
        dlx.branchLimit = branchLimit;
        dlx.nodeLimit = nodeLimit;
        dlx.deadline = deadline;
        dlx.rng.seed(1234567u + 1000003u * a);

        if (dlx.solve()) {
            answerIds = dlx.answer;
            break;
        }
    }

    if (answerIds.empty()) {
        return 0;
    }

    vector<RowInfo> chosen;
    chosen.reserve(answerIds.size());

    for (int id : answerIds) {
        chosen.push_back(rows[id]);
    }

    sort(chosen.begin(), chosen.end(), [](const RowInfo& a, const RowInfo& b) {
        return a.start < b.start;
    });

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

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

    cout << '\n';

    return 0;
}
0