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

• 問題: No.1743 Permutation Code
• ユーザー: harurun
• 提出日時: 2026-07-09 05:16:56
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 8,295 bytes
• コンパイル時間: 1,641 ms
• コンパイル使用メモリ: 236,952 KB
• 実行使用メモリ: 9,072 KB
• 最終ジャッジ日時: 2026-07-09 05:17:32
• 合計ジャッジ時間: 13,206 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

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

const int INF = 1e9;

string C;
int L, N, M;

struct Occ {
    int s;
    unsigned short v;
    unsigned char len;
    int nextStart;
    int nextVal;
};

vector<Occ> occ;
vector<int> headStart;
vector<int> headVal;

vector<unsigned char> activeOcc;
vector<unsigned char> coveredVal;
vector<unsigned char> coveredPos;

vector<int> cntVal;
vector<int> cntPos;

vector<int> chosenOcc;

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_len(int x) {
    return 32 - __builtin_clz((unsigned)x);
}

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

    void init(int sz) {
        n = 1;
        while (n < sz) n <<= 1;
        seg.assign(2 * n, {INF, -1});
    }

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

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

    pair<int, int> min_all() const {
        return seg[1];
    }
};

SegTree st;

// column id:
// 0 .. N-1       : value 1..N
// N .. N+L-1     : position 0..L-1
int val_col(int v) {
    return v - 1;
}

int pos_col(int p) {
    return N + p;
}

int occ_end(int id) {
    return occ[id].s + occ[id].len;
}

bool overlap(int a, int b) {
    int l1 = occ[a].s;
    int r1 = occ_end(a);
    int l2 = occ[b].s;
    int r2 = occ_end(b);
    return l1 < r2 && l2 < r1;
}

struct Change {
    int type;
    int id;
};

vector<Change> hist;

void dec_val(int v) {
    cntVal[v]--;
    if (!coveredVal[v]) {
        st.set_val(val_col(v), cntVal[v]);
    }
}

void inc_val(int v) {
    cntVal[v]++;
    if (!coveredVal[v]) {
        st.set_val(val_col(v), cntVal[v]);
    }
}

void dec_pos(int p) {
    cntPos[p]--;
    if (!coveredPos[p]) {
        st.set_val(pos_col(p), cntPos[p]);
    }
}

void inc_pos(int p) {
    cntPos[p]++;
    if (!coveredPos[p]) {
        st.set_val(pos_col(p), cntPos[p]);
    }
}

void deactivate_occ(int id) {
    if (!activeOcc[id]) return;

    activeOcc[id] = 0;
    hist.push_back({0, id});

    int v = occ[id].v;
    dec_val(v);
    hist.push_back({1, v});

    int s = occ[id].s;
    int t = occ_end(id);

    for (int p = s; p < t; p++) {
        dec_pos(p);
        hist.push_back({2, p});
    }
}

void undo(int checkpoint) {
    while ((int)hist.size() > checkpoint) {
        auto c = hist.back();
        hist.pop_back();

        if (c.type == 0) {
            activeOcc[c.id] = 1;
        } else if (c.type == 1) {
            inc_val(c.id);
        } else if (c.type == 2) {
            inc_pos(c.id);
        } else if (c.type == 3) {
            coveredVal[c.id] = 0;
            st.set_val(val_col(c.id), cntVal[c.id]);
        } else if (c.type == 4) {
            coveredPos[c.id] = 0;
            st.set_val(pos_col(c.id), cntPos[c.id]);
        }
    }
}

void cover_value(int v) {
    coveredVal[v] = 1;
    hist.push_back({3, v});
    st.set_val(val_col(v), INF);
}

void cover_position(int p) {
    coveredPos[p] = 1;
    hist.push_back({4, p});
    st.set_val(pos_col(p), INF);
}

bool select_occ(int id) {
    if (!activeOcc[id]) return false;

    int v = occ[id].v;
    int s = occ[id].s;
    int t = occ_end(id);

    if (coveredVal[v]) return false;

    for (int p = s; p < t; p++) {
        if (coveredPos[p]) return false;
    }

    cover_value(v);

    for (int p = s; p < t; p++) {
        cover_position(p);
    }

    // 同じ値を持つ候補を消す
    for (int e = headVal[v]; e != -1; e = occ[e].nextVal) {
        if (activeOcc[e]) {
            deactivate_occ(e);
        }
    }

    // 区間 [s,t) と重なる候補を消す
    int from = max(0, s - M + 1);
    int to = min(L - 1, t - 1);

    for (int p = from; p <= to; p++) {
        for (int e = headStart[p]; e != -1; e = occ[e].nextStart) {
            if (activeOcc[e] && overlap(id, e)) {
                deactivate_occ(e);
            }
        }
    }

    return true;
}

vector<int> collect_rows_for_value(int v) {
    vector<int> rows;

    for (int e = headVal[v]; e != -1; e = occ[e].nextVal) {
        if (activeOcc[e]) {
            rows.push_back(e);
        }
    }

    return rows;
}

vector<int> collect_rows_for_position(int p) {
    vector<int> rows;

    int from = max(0, p - M + 1);

    for (int s = from; s <= p; s++) {
        for (int e = headStart[s]; e != -1; e = occ[e].nextStart) {
            if (activeOcc[e]) {
                int l = occ[e].s;
                int r = occ_end(e);

                if (l <= p && p < r) {
                    rows.push_back(e);
                }
            }
        }
    }

    return rows;
}

int impact(int id) {
    int res = 0;

    int v = occ[id].v;
    int s = occ[id].s;
    int t = occ_end(id);

    for (int e = headVal[v]; e != -1; e = occ[e].nextVal) {
        if (activeOcc[e]) res++;
    }

    int from = max(0, s - M + 1);
    int to = min(L - 1, t - 1);

    for (int p = from; p <= to; p++) {
        for (int e = headStart[p]; e != -1; e = occ[e].nextStart) {
            if (activeOcc[e] && overlap(id, e)) {
                res++;
            }
        }
    }

    return res;
}

bool dfs(int usedCount) {
    if (usedCount == N) {
        return true;
    }

    auto [mn, col] = st.min_all();

    if (mn == INF) {
        return true;
    }

    if (mn == 0) {
        return false;
    }

    vector<int> rows;

    if (col < N) {
        int v = col + 1;
        rows = collect_rows_for_value(v);
    } else {
        int p = col - N;
        rows = collect_rows_for_position(p);
    }

    if (rows.empty()) {
        return false;
    }

    sort(rows.begin(), rows.end(), [](int a, int b) {
        return impact(a) > impact(b);
    });

    for (int id : rows) {
        int checkpoint = hist.size();

        if (select_occ(id)) {
            chosenOcc.push_back(id);

            if (dfs(usedCount + 1)) {
                return true;
            }

            chosenOcc.pop_back();
        }

        undo(checkpoint);
    }

    return false;
}

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

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

    long long lo = 1, hi = 65535;

    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);

    headStart.assign(L, -1);
    headVal.assign(N + 1, -1);
    cntVal.assign(N + 1, 0);
    cntPos.assign(L, 0);

    occ.reserve((long long)L * M / 2);

    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)occ.size();

            Occ o;
            o.s = s;
            o.v = (unsigned short)v;
            o.len = (unsigned char)len;
            o.nextStart = headStart[s];
            o.nextVal = headVal[v];

            headStart[s] = id;
            headVal[v] = id;

            occ.push_back(o);

            cntVal[v]++;

            for (int p = s; p < t; p++) {
                cntPos[p]++;
            }
        }
    }

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

    for (int p = 0; p < L; p++) {
        if (cntPos[p] == 0) return 0;
    }

    activeOcc.assign(occ.size(), 1);
    coveredVal.assign(N + 1, 0);
    coveredPos.assign(L, 0);

    st.init(N + L);

    for (int v = 1; v <= N; v++) {
        st.set_val(val_col(v), cntVal[v]);
    }

    for (int p = 0; p < L; p++) {
        st.set_val(pos_col(p), cntPos[p]);
    }

    chosenOcc.reserve(N);

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

    sort(chosenOcc.begin(), chosenOcc.end(), [](int a, int b) {
        return occ[a].s < occ[b].s;
    });

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

    cout << '\n';

    return 0;
}