Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Treat operation as choosing either no edge, or one edge whose endpoints are exactly apart. The annoying global rule is that every length can be used only once.
Processing symmetric endpoints of an interval is natural: the pair uses length , and that length appears at exactly this recursion layer.
If , the endpoints can be deleted together. If , keep one unresolved outside the interval and try to delete it with a future endpoint/middle position.
The hard part is when the carried is too far away to pair with the current interval. Reflect it across the interval center; this creates a symmetric block where the remaining usable lengths are consecutive with the same parity.
Use explicit repair patterns only for the near-balanced symmetric blocks , , . When the interval gets small, stop the madness and finish a size- block with bitmask DP.
Let . Operation either does nothing, or flips one pair . So we are spending each distance at most once.
The key recursive idea is to process symmetric endpoints of an interval. For endpoints , the required operation length is exactly , so every recursion layer naturally owns one distance. If the two endpoint bits are equal, they are easy:
If the endpoint bits differ, flipping would only move the problem around. Instead, we keep one unresolved as a carry position outside the current interval. Later, when processing length , we try to flip or if the other endpoint lies strictly inside the interval. This deletes the carried and lets recursion continue.
Even is handled first. We spend the largest length on , then solve the first positions as an odd-length instance. Position may remain dirty, but one leftover is fine.
For odd , choose an odd center-ish point mid. The left side is handled by an outward procedure solve_completely(l,r,p). It expands from the middle and guarantees that after it finishes, the whole left part contributes at most one carried . This procedure is clean: equal endpoint bits are deleted directly; unequal endpoint bits are fixed using the previous carry if it exists, then the new carry becomes the endpoint that is currently .
The right side is handled by solve_partially(l,r,p), moving inward. With no carry, equal endpoints are deleted and unequal endpoints create a carry. With a carry, we first try the obvious deletion using the current length .
The only nasty case is when that obvious deletion is impossible. Assume the carry is on the left, . Reflect it through the center of and call the reflected point , so
Now the relevant block has shape
The unused lengths available inside this symmetric block are
That means we can use a sequence of decreasing same-parity lengths. The implementation encodes fixed repair patterns for exactly the important balanced cases:
For each of these and each endpoint mask , the pattern spends those decreasing lengths and replaces the bad carry by a new carry within distance at most of the current boundary. This is ugly casework, but it is small, deterministic, and very much better than pretending a cute one-line invariant exists. Sometimes constructive problems just make you pay rent.
If is not one of those three values, recursion keeps shrinking the interval until it becomes one. A failed carry deletion can only happen when the carry is far compared with the interval. After a repair, the next possible failure requires the active interval to have shrunk by about a factor of . Therefore only a few carries can survive before the interval becomes tiny.
For the tiny interval we use a precomputed DP on bits. The DP works backwards. At size , every mask with or set bits is acceptable. Then for lengths , we mark all masks that can become acceptable after either skipping the length or flipping one pair at that length. This gives an instruction table for every -bit mask, and replaying it leaves at most one in that block.
Correctness comes from the following invariants:
solve_completely leaves at most one unresolved from the left part;solve_partially either deletes its carry, repairs a bad carry inside a symmetric block, or shrinks the interval while preserving the one-carry invariant;The repair step is the only nontrivial construction. The code's pattern table is the formal certificate: every listed move uses the next available same-parity length, and direct parity tracking shows the resulting carry is near the boundary, so recursion remains valid.
With , the geometric shrink bound plus the final DP keeps the total number of remaining ones at most .
The precomputation costs once. Each test case is processed in time. Memory usage is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int DB = 20;
const int MSK = 1 << DB;
bool ok[DB + 1][MSK];
int pre[DB + 1][MSK];
void build_dp() {
ok[DB][0] = true;
for (int i = 0; i < DB; ++i) ok[DB][1 << i] = true;
for (int len = DB; len >= 2; len -= 2) {
for (int mask = 0; mask < MSK; ++mask) {
if (!ok[len][mask]) continue;
if (!ok[len - 2][mask]) {
ok[len - 2][mask] = true;
pre[len - 2][mask] = -1;
}
int d = len - 1;
for (int i = 0; i + d < DB; ++i) {
int nxt = mask ^ (1 << i) ^ (1 << (i + d));
if (!ok[len - 2][nxt]) {
ok[len - 2][nxt] = true;
pre[len - 2][nxt] = i;
}
}
}
}
}
vector<int> get_dp_ops(int mask) {
vector<int> res(DB + 1, -1);
for (int len = 0; len < DB; len += 2) {
int pos = pre[len][mask];
res[len + 1] = pos;
if (pos != -1) {
mask ^= 1 << pos;
mask ^= 1 << (pos + len + 1);
}
}
return res;
}
struct Solver {
int n, real_n;
string s;
vector<int> a, ans;
void apply_op(int x, int y) {
if (x > y) swap(x, y);
ans[y - x] = x;
a[x] ^= 1;
a[y] ^= 1;
}
void undo_op(int x, int y) {
if (x > y) swap(x, y);
if (!ans[y - x]) return;
ans[y - x] = 0;
a[x] ^= 1;
a[y] ^= 1;
}
int solve_completely(int l, int r, int p) {
if (l == 0) return p;
if (a[l] == a[r]) {
if (a[l]) apply_op(l, r);
return solve_completely(l - 1, r + 1, p);
}
if (p) apply_op(p, p + r - l);
return a[l] ? solve_completely(l - 1, r + 1, l)
: solve_completely(l - 1, r + 1, r);
}
void solve_partially(int l, int r, int p, bool repaired) {
if (l >= r) return;
if (!p) {
if (a[l] == a[r]) {
if (a[l]) apply_op(l, r);
solve_partially(l + 1, r - 1, 0, false);
} else {
solve_partially(l + 1, r - 1, a[l] ? l : r, false);
}
return;
}
if (r - l + 1 == DB) {
int mask = 0;
for (int i = l; i <= r; ++i) mask |= a[i] << (i - l);
auto res = get_dp_ops(mask);
for (int len = r - l; len >= 1; len -= 2) {
if (res[len] != -1) apply_op(l + res[len], l + res[len] + len);
}
return;
}
int x = l + r - p, y = p;
if (x > y) swap(x, y);
int A = l - x;
int B = r - l + 1;
if (!repaired && B >= 10 && abs(A - B) == 1) {
for (int i = x + 1; i < l; ++i) undo_op(i, l + r - i);
int len = y - x - 2;
auto use = [&](int v) {
int left = x + v;
int right = left + len;
len -= 2;
if (p > l) {
left = l + r - left;
right = l + r - right;
}
apply_op(left, right);
};
int type = a[l] | (a[r] << 1);
if (p > r) type = a[r] | (a[l] << 1);
if (A == B - 1) {
if (type == 0) {
for (int i = 0; i <= B - 4; ++i) use(i);
use(2 * B - 5); use(B - 3);
} else if (type == 1) {
use(0);
for (int i = 3; i <= B - 3; i += 2) use(i), use(i - 1);
use(B - 1); use(1);
} else if (type == 2) {
for (int i = 0; i <= B - 3; ++i) use(i);
use(2 * B - 3);
} else {
for (int i = 1; i <= B - 2; ++i) use(i);
use(0);
}
} else if (A == B) {
if (type == 0) {
for (int i = 0; i <= B - 2; ++i) use(i);
use(2 * B - 1);
} else if (type == 1) {
use(1); use(0);
if (B % 3 == 2) {
for (int i = 3; i <= B - 5; i += 3) use(i + 1), use(i + 2), use(i);
use(B - 1); use(B); use(2);
} else if (B % 3 == 0) {
for (int i = 3; i <= B - 6; i += 3) use(i + 1), use(i + 2), use(i);
use(B - 3); use(B); use(B - 1); use(2);
} else {
for (int i = 3; i <= B - 7; i += 3) use(i + 1), use(i + 2), use(i);
use(B - 3); use(B - 4); use(B); use(B - 1); use(2);
}
} else if (type == 2) {
use(1); use(0);
for (int i = 3; i <= B - 3; i += 2) use(i), use(i - 1);
use(B - 1); use(2 * B - 2);
} else {
use(0);
for (int i = 3; i <= B - 1; i += 2) use(i), use(i - 1);
use(1);
}
} else {
if (type == 0) {
for (int i = 1; i <= B; ++i) use(i);
use(0);
} else if (type == 1) {
for (int i = 1; i < B; ++i) use(i);
use(0); use(B);
} else if (type == 2) {
for (int i = 1; i <= B - 1; i += 2) use(i), use(i - 1);
use(2 * B);
} else {
if (B % 3 == 2) {
use(0); use(1);
for (int i = 3; i <= B - 2; i += 3) use(i + 2), use(i), use(i + 1);
use(2);
} else if (B % 3 == 0) {
use(1); use(0);
for (int i = 3; i <= B - 3; i += 3) use(i + 1), use(i + 2), use(i);
use(B); use(2);
} else {
use(1); use(0);
for (int i = 4; i <= B - 3; i += 3) use(i), use(i + 1), use(i - 1);
use(B); use(B - 1); use(2);
}
}
}
for (int i = x; i <= l; ++i) if (a[i]) return solve_partially(l + 1, r - 1, i, true);
for (int i = r; i <= y; ++i) if (a[i]) return solve_partially(l + 1, r - 1, i, true);
solve_partially(l + 1, r - 1, 0, true);
return;
}
if (a[l] && a[r]) {
apply_op(l, r);
solve_partially(l + 1, r - 1, p, repaired);
return;
}
int len = r - l;
auto down = [&]() {
if (a[l]) solve_partially(l + 1, r - 1, l, false);
else if (a[r]) solve_partially(l + 1, r - 1, r, false);
else solve_partially(l + 1, r - 1, 0, false);
};
if (p + len > l && p + len < r) {
apply_op(p, p + len);
down();
} else if (p - len > l && p - len < r) {
apply_op(p, p - len);
down();
} else {
down();
}
}
void run() {
cin >> real_n >> s;
n = real_n;
a.assign(real_n + 2, 0);
ans.assign(real_n / 2 + 2, 0);
for (int i = 1; i <= real_n; ++i) a[i] = s[i - 1] - '0';
if (n % 2 == 0) {
apply_op(n - n / 2, n);
--n;
}
int mid = (n + 1) / 2;
if (mid % 2 == 0) --mid;
solve_completely(mid / 2, mid / 2 + 2, a[mid / 2 + 1] ? mid / 2 + 1 : 0);
solve_partially(mid + 1, n, 0, false);
for (int i = 1; i <= real_n / 2; ++i) {
cout << ans[i] << (i == real_n / 2 ? '\n' : ' ');
}
}
};
int main() {
setIO();
build_dp();
int T;
cin >> T;
while (T--) {
Solver solver;
solver.run();
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int DB = 20;
const int MSK = 1 << DB;
bool ok[DB + 1][MSK];
int pre[DB + 1][MSK];
void build_dp() {
ok[DB][0] = true;
for (int i = 0; i < DB; ++i) ok[DB][1 << i] = true;
for (int len = DB; len >= 2; len -= 2) {
for (int mask = 0; mask < MSK; ++mask) {
if (!ok[len][mask]) continue;
if (!ok[len - 2][mask]) {
ok[len - 2][mask] = true;
pre[len - 2][mask] = -1;
}
int d = len - 1;
for (int i = 0; i + d < DB; ++i) {
int nxt = mask ^ (1 << i) ^ (1 << (i + d));
if (!ok[len - 2][nxt]) {
ok[len - 2][nxt] = true;
pre[len - 2][nxt] = i;
}
}
}
}
}
vector<int> get_dp_ops(int mask) {
vector<int> res(DB + 1, -1);
for (int len = 0; len < DB; len += 2) {
int pos = pre[len][mask];
res[len + 1] = pos;
if (pos != -1) {
mask ^= 1 << pos;
mask ^= 1 << (pos + len + 1);
}
}
return res;
}
struct Solver {
int n, real_n;
string s;
vector<int> a, ans;
void apply_op(int x, int y) {
if (x > y) swap(x, y);
ans[y - x] = x;
a[x] ^= 1;
a[y] ^= 1;
}
void undo_op(int x, int y) {
if (x > y) swap(x, y);
if (!ans[y - x]) return;
ans[y - x] = 0;
a[x] ^= 1;
a[y] ^= 1;
}
int solve_completely(int l, int r, int p) {
if (l == 0) return p;
if (a[l] == a[r]) {
if (a[l]) apply_op(l, r);
return solve_completely(l - 1, r + 1, p);
}
if (p) apply_op(p, p + r - l);
return a[l] ? solve_completely(l - 1, r + 1, l)
: solve_completely(l - 1, r + 1, r);
}
void solve_partially(int l, int r, int p, bool repaired) {
if (l >= r) return;
if (!p) {
if (a[l] == a[r]) {
if (a[l]) apply_op(l, r);
solve_partially(l + 1, r - 1, 0, false);
} else {
solve_partially(l + 1, r - 1, a[l] ? l : r, false);
}
return;
}
if (r - l + 1 == DB) {
int mask = 0;
for (int i = l; i <= r; ++i) mask |= a[i] << (i - l);
auto res = get_dp_ops(mask);
for (int len = r - l; len >= 1; len -= 2) {
if (res[len] != -1) apply_op(l + res[len], l + res[len] + len);
}
return;
}
int x = l + r - p, y = p;
if (x > y) swap(x, y);
int A = l - x;
int B = r - l + 1;
if (!repaired && B >= 10 && abs(A - B) == 1) {
for (int i = x + 1; i < l; ++i) undo_op(i, l + r - i);
int len = y - x - 2;
auto use = [&](int v) {
int left = x + v;
int right = left + len;
len -= 2;
if (p > l) {
left = l + r - left;
right = l + r - right;
}
apply_op(left, right);
};
int type = a[l] | (a[r] << 1);
if (p > r) type = a[r] | (a[l] << 1);
if (A == B - 1) {
if (type == 0) {
for (int i = 0; i <= B - 4; ++i) use(i);
use(2 * B - 5); use(B - 3);
} else if (type == 1) {
use(0);
for (int i = 3; i <= B - 3; i += 2) use(i), use(i - 1);
use(B - 1); use(1);
} else if (type == 2) {
for (int i = 0; i <= B - 3; ++i) use(i);
use(2 * B - 3);
} else {
for (int i = 1; i <= B - 2; ++i) use(i);
use(0);
}
} else if (A == B) {
if (type == 0) {
for (int i = 0; i <= B - 2; ++i) use(i);
use(2 * B - 1);
} else if (type == 1) {
use(1); use(0);
if (B % 3 == 2) {
for (int i = 3; i <= B - 5; i += 3) use(i + 1), use(i + 2), use(i);
use(B - 1); use(B); use(2);
} else if (B % 3 == 0) {
for (int i = 3; i <= B - 6; i += 3) use(i + 1), use(i + 2), use(i);
use(B - 3); use(B); use(B - 1); use(2);
} else {
for (int i = 3; i <= B - 7; i += 3) use(i + 1), use(i + 2), use(i);
use(B - 3); use(B - 4); use(B); use(B - 1); use(2);
}
} else if (type == 2) {
use(1); use(0);
for (int i = 3; i <= B - 3; i += 2) use(i), use(i - 1);
use(B - 1); use(2 * B - 2);
} else {
use(0);
for (int i = 3; i <= B - 1; i += 2) use(i), use(i - 1);
use(1);
}
} else {
if (type == 0) {
for (int i = 1; i <= B; ++i) use(i);
use(0);
} else if (type == 1) {
for (int i = 1; i < B; ++i) use(i);
use(0); use(B);
} else if (type == 2) {
for (int i = 1; i <= B - 1; i += 2) use(i), use(i - 1);
use(2 * B);
} else {
if (B % 3 == 2) {
use(0); use(1);
for (int i = 3; i <= B - 2; i += 3) use(i + 2), use(i), use(i + 1);
use(2);
} else if (B % 3 == 0) {
use(1); use(0);
for (int i = 3; i <= B - 3; i += 3) use(i + 1), use(i + 2), use(i);
use(B); use(2);
} else {
use(1); use(0);
for (int i = 4; i <= B - 3; i += 3) use(i), use(i + 1), use(i - 1);
use(B); use(B - 1); use(2);
}
}
}
for (int i = x; i <= l; ++i) if (a[i]) return solve_partially(l + 1, r - 1, i, true);
for (int i = r; i <= y; ++i) if (a[i]) return solve_partially(l + 1, r - 1, i, true);
solve_partially(l + 1, r - 1, 0, true);
return;
}
if (a[l] && a[r]) {
apply_op(l, r);
solve_partially(l + 1, r - 1, p, repaired);
return;
}
int len = r - l;
auto down = [&]() {
if (a[l]) solve_partially(l + 1, r - 1, l, false);
else if (a[r]) solve_partially(l + 1, r - 1, r, false);
else solve_partially(l + 1, r - 1, 0, false);
};
if (p + len > l && p + len < r) {
apply_op(p, p + len);
down();
} else if (p - len > l && p - len < r) {
apply_op(p, p - len);
down();
} else {
down();
}
}
void run() {
cin >> real_n >> s;
n = real_n;
a.assign(real_n + 2, 0);
ans.assign(real_n / 2 + 2, 0);
for (int i = 1; i <= real_n; ++i) a[i] = s[i - 1] - '0';
if (n % 2 == 0) {
apply_op(n - n / 2, n);
--n;
}
int mid = (n + 1) / 2;
if (mid % 2 == 0) --mid;
solve_completely(mid / 2, mid / 2 + 2, a[mid / 2 + 1] ? mid / 2 + 1 : 0);
solve_partially(mid + 1, n, 0, false);
for (int i = 1; i <= real_n / 2; ++i) {
cout << ans[i] << (i == real_n / 2 ? '\n' : ' ');
}
}
};
int main() {
setIO();
build_dp();
int T;
cin >> T;
while (T--) {
Solver solver;
solver.run();
}
}