結果
| 問題 | No.1743 Permutation Code |
| ユーザー |
 harurun
|
| 提出日時 | 2026-07-10 12:45:53 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 14,124 bytes |
| 記録 | |
| コンパイル時間 | 1,768 ms |
| コンパイル使用メモリ | 239,420 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-07-10 12:46:08 |
| 合計ジャッジ時間 | 12,120 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 TLE * 1 -- * 22 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
struct Solver {
string C;
int L = 0, N = 0, M = 0, H = 0;
vector<int> zr; // token i = 1 followed by zr[i] zeros
vector<vector<int>> candAt; // candidate values whose word can start at token i
vector<int> parent, depth, subtree, rem;
vector<int> occ, last;
vector<unsigned char> used;
// For each token position p, mandCnt[p] is the number of unused values
// whose only remaining possible start is p. mandXor retrieves it if unique.
vector<int> mandCnt, mandXor, mandWhere;
set<int> mandPos;
int badMand = 0;
vector<int> answer;
enum UndoType : int {
U_REM = 0,
U_USED = 1,
U_OCC = 2,
U_MAND_ADD = 3,
U_MAND_REMOVE = 4,
U_ANSWER = 5,
};
struct Undo {
int a;
int b;
int type;
};
vector<Undo> undo;
struct State {
int token; // current token index
int value; // current prefix value
int wordStart; // token index where current word started
};
enum ActionKind : int { CONTINUE_WORD = 0, END_WORD = 1 };
struct Action {
ActionKind kind;
int nextValue;
};
struct Decision {
size_t checkpoint;
State base;
Action second;
};
static long long totalLength(int n) {
long long ret = 0;
for (int b = 1, lo = 1; lo <= n; ++b, lo <<= 1) {
int hi = min(n, (1 << b) - 1);
ret += 1LL * b * (hi - lo + 1);
if (lo > n / 2) break;
}
return ret;
}
static int bitLength(int x) {
return 32 - __builtin_clz((unsigned)x);
}
bool isAncestor(int a, int b) const {
if (depth[a] > depth[b]) return false;
while (depth[b] > depth[a]) b = parent[b];
return a == b;
}
void rawAddMandatory(int p, int v) {
int old = mandCnt[p];
if (old == 0) mandPos.insert(p);
if (old == 1) ++badMand;
++mandCnt[p];
mandXor[p] ^= v;
mandWhere[v] = p;
}
void rawRemoveMandatory(int p, int v) {
int old = mandCnt[p];
if (old == 2) --badMand;
--mandCnt[p];
mandXor[p] ^= v;
mandWhere[v] = -1;
if (mandCnt[p] == 0) mandPos.erase(p);
}
void addMandatory(int p, int v) {
rawAddMandatory(p, v);
undo.push_back({p, v, U_MAND_ADD});
}
void removeMandatory(int p, int v) {
rawRemoveMandatory(p, v);
undo.push_back({p, v, U_MAND_REMOVE});
}
void decRem(int v) {
--rem[v];
undo.push_back({v, 0, U_REM});
}
void markUsed(int v) {
used[v] = 1;
undo.push_back({v, 0, U_USED});
}
void decOcc(int v) {
--occ[v];
undo.push_back({v, 0, U_OCC});
}
void pushAnswer(int v) {
answer.push_back(v);
undo.push_back({0, 0, U_ANSWER});
}
void rollback(size_t checkpoint) {
while (undo.size() > checkpoint) {
Undo u = undo.back();
undo.pop_back();
switch (u.type) {
case U_REM:
++rem[u.a];
break;
case U_USED:
used[u.a] = 0;
break;
case U_OCC:
++occ[u.a];
break;
case U_MAND_ADD:
rawRemoveMandatory(u.a, u.b);
break;
case U_MAND_REMOVE:
rawAddMandatory(u.a, u.b);
break;
case U_ANSWER:
answer.pop_back();
break;
}
}
}
// The start p is not a boundary. Therefore every still-unused candidate
// occurrence beginning at p disappears.
bool appearsAt(int p, int v) const {
const auto& a = candAt[p];
return find(a.begin(), a.end(), v) != a.end();
}
bool skipStart(int p, int pendingStart) {
for (int v : candAt[p]) {
if (used[v]) continue;
if (occ[v] <= 1) return false;
int before = occ[v];
decOcc(v);
if (before == 2) {
int soleStart = appearsAt(pendingStart, v) ? pendingStart : last[v];
addMandatory(soleStart, v);
if (badMand) return false;
}
}
return true;
}
// Select value chosen at the pending boundary p, and expire every other
// candidate occurrence beginning at p.
bool selectWord(int p, int chosen) {
if (chosen < 1 || chosen > N || used[chosen]) return false;
bool found = false;
for (int v : candAt[p]) {
if (v == chosen) {
found = true;
break;
}
}
if (!found) return false;
if (occ[chosen] == 1) removeMandatory(mandWhere[chosen], chosen);
markUsed(chosen);
for (int v : candAt[p]) {
if (v == chosen || used[v]) continue;
if (occ[v] <= 1) return false;
int before = occ[v];
decOcc(v);
if (before == 2) {
addMandatory(last[v], v);
if (badMand) return false;
}
}
pushAnswer(chosen);
return true;
}
bool basicConsistent(const State& s) const {
if (badMand) return false;
if (!mandPos.empty() && *mandPos.begin() < s.wordStart) return false;
// A mandatory boundary already crossed inside the current word.
if (!mandPos.empty() && *mandPos.begin() <= s.token &&
*mandPos.begin() != s.wordStart) return false;
return true;
}
int forcedTarget(const State& s) const {
if (mandCnt[s.wordStart] == 1) return mandXor[s.wordStart];
return 0;
}
vector<Action> actions(const State& s) const {
vector<Action> out;
if (!basicConsistent(s)) return out;
int target = forcedTarget(s);
if (target && !isAncestor(s.value, target)) return out;
bool mustEndForQuota = (rem[s.value] == 0 && !used[s.value]);
// End the current word after token s.token.
bool canEnd = !used[s.value];
if (target && target != s.value) canEnd = false;
if (canEnd) {
int q = s.token + 1;
int root = 1 << zr[q];
if (root <= N && rem[root] > 0) {
out.push_back({END_WORD, root});
}
}
// Continue the current word with token s.token+1.
bool canContinue = !mustEndForQuota;
int q = s.token + 1;
if (mandCnt[q] != 0) canContinue = false; // q has to be a boundary
long long child64 = (2LL * s.value + 1) << zr[q];
int child = child64 <= N ? (int)child64 : N + 1;
if (child64 > N || rem[child] <= 0) canContinue = false;
if (target) {
if (s.value == target) canContinue = false;
else if (child <= N && !isAncestor(child, target)) canContinue = false;
}
if (canContinue) out.push_back({CONTINUE_WORD, child});
return out;
}
bool applyAction(const State& s, const Action& a, State& ns) {
int q = s.token + 1;
if (a.kind == CONTINUE_WORD) {
if (!skipStart(q, s.wordStart)) return false;
if (rem[a.nextValue] <= 0) return false;
decRem(a.nextValue);
ns = {q, a.nextValue, s.wordStart};
return basicConsistent(ns);
}
if (!selectWord(s.wordStart, s.value)) return false;
if (rem[a.nextValue] <= 0) return false;
decRem(a.nextValue);
ns = {q, a.nextValue, q};
return basicConsistent(ns);
}
bool finish(const State& s) {
if (!basicConsistent(s)) return false;
int target = forcedTarget(s);
if (target && target != s.value) return false;
if (used[s.value]) return false;
if (rem[s.value] != 0) return false;
if (!selectWord(s.wordStart, s.value)) return false;
if ((int)answer.size() != N) return false;
if (!mandPos.empty() || badMand) return false;
return true;
}
// Lower score is tried first. This only affects search order.
long long actionScore(const State&, const Action& a) const {
return a.kind == END_WORD ? 0 : 1;
}
bool search() {
if (H == 0) return false;
int root = 1 << zr[0];
if (root > N || rem[root] <= 0) return false;
decRem(root);
State st{0, root, 0};
vector<Decision> decisions;
while (true) {
bool contradiction = false;
while (true) {
if (!basicConsistent(st)) {
contradiction = true;
break;
}
if (st.token == H - 1) {
size_t cp = undo.size();
if (finish(st)) return true;
rollback(cp);
contradiction = true;
break;
}
vector<Action> as = actions(st);
if (as.empty()) {
contradiction = true;
break;
}
if (as.size() == 1) {
State ns;
if (!applyAction(st, as[0], ns)) {
contradiction = true;
break;
}
st = ns;
continue;
}
if (actionScore(st, as[1]) < actionScore(st, as[0])) {
swap(as[0], as[1]);
}
Decision d{undo.size(), st, as[1]};
decisions.push_back(d);
State ns;
if (!applyAction(st, as[0], ns)) {
// Try the second branch immediately.
Decision back = decisions.back();
decisions.pop_back();
rollback(back.checkpoint);
st = back.base;
if (!applyAction(st, back.second, ns)) {
contradiction = true;
break;
}
}
st = ns;
}
if (!contradiction) continue;
bool resumed = false;
while (!decisions.empty()) {
Decision d = decisions.back();
decisions.pop_back();
rollback(d.checkpoint);
st = d.base;
State ns;
if (applyAction(st, d.second, ns)) {
st = ns;
resumed = true;
break;
}
}
if (!resumed) return false;
}
}
bool initialize() {
L = (int)C.size();
int lo = 1, hi = 65535;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (totalLength(mid) >= L) hi = mid;
else lo = mid + 1;
}
if (totalLength(lo) != L) return false;
N = lo;
M = bitLength(N);
if (C.empty() || C[0] != '1') return false;
for (int i = 0; i < L;) {
if (C[i] != '1') return false;
int j = i + 1;
while (j < L && C[j] == '0') ++j;
zr.push_back(j - i - 1);
i = j;
}
H = (int)zr.size();
parent.assign(N + 1, 0);
depth.assign(N + 1, 0);
subtree.assign(N + 1, 1);
for (int x = 1; x <= N; ++x) {
if ((x & (x - 1)) == 0) {
parent[x] = 0;
depth[x] = 0;
} else {
int a = __builtin_ctz((unsigned)x);
parent[x] = ((x >> a) - 1) >> 1;
depth[x] = depth[parent[x]] + 1;
}
}
for (int x = N; x >= 1; --x) {
if (parent[x]) subtree[parent[x]] += subtree[x];
}
long long sumSubtree = 0;
for (int x = 1; x <= N; ++x) sumSubtree += subtree[x];
if (sumSubtree != H) return false;
rem = subtree;
candAt.assign(H, {});
occ.assign(N + 1, 0);
last.assign(N + 1, -1);
for (int s = 0; s < H; ++s) {
int bits = 0;
int v = 0;
candAt[s].reserve(M);
for (int t = s; t < H; ++t) {
bits += 1 + zr[t];
if (bits > M) break;
if (t == s) v = 1 << zr[t];
else v = ((v << 1) | 1) << zr[t];
if (v > N) break;
candAt[s].push_back(v);
++occ[v];
last[v] = s;
}
}
used.assign(N + 1, 0);
mandCnt.assign(H, 0);
mandXor.assign(H, 0);
mandWhere.assign(N + 1, -1);
for (int v = 1; v <= N; ++v) {
if (occ[v] == 0) return false;
if (occ[v] == 1) rawAddMandatory(last[v], v);
}
if (badMand) return false;
answer.reserve(N);
undo.reserve((size_t)H * 4);
return true;
}
bool verify() const {
if ((int)answer.size() != N) return false;
vector<unsigned char> seen(N + 1, 0);
string rebuilt;
rebuilt.reserve(L);
for (int x : answer) {
if (x < 1 || x > N || seen[x]) return false;
seen[x] = 1;
string s;
for (int y = x; y; y >>= 1) s.push_back(char('0' + (y & 1)));
reverse(s.begin(), s.end());
rebuilt += s;
}
return rebuilt == C;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Solver solver;
cin >> solver.C;
if (!solver.initialize()) return 0;
if (!solver.search()) return 0;
if (!solver.verify()) return 0;
for (int i = 0; i < solver.N; ++i) {
if (i) cout << ' ';
cout << solver.answer[i];
}
cout << '\n';
return 0;
}