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.
A move exists exactly when there is an inversion: some 1 before some 0. If the string is already non-decreasing, Bob wins immediately.
Forget the current order for a second. Count the zeros. In the final sorted string, the first positions must be 0, where is the number of zeros.
Look for positions that disagree with that final sorted string: 1s among the first positions, and 0s after position .
Those wrong positions, in increasing order, always form a sequence of some 1s followed by some 0s. That is exactly the non-increasing pattern a move is allowed to choose.
Choose all wrong positions. Sorting only those positions fixes every mismatch at once, so any unsorted string is an immediate Alice win. No deep game tree, no spooky minimax nonsense.
Let be the number of zeros in . If the string were fully sorted, then positions would all be 0, and positions would all be 1.
So compare the current string to that target shape:
Now list all wrong positions in increasing order. First we see the wrong positions from the prefix , and all of those characters are 1. Then we see the wrong positions from the suffix , and all of those characters are 0.
Therefore, the chosen characters look like
which is non-increasing. So this set of indices is legal to choose.
Also, the number of wrong 1s in the first positions equals the number of wrong 0s after position . Why? The whole string has exactly zeros. If the first positions are missing zeros, those zeros must be sitting in the suffix. So the wrong positions contain ones followed by zeros.
When Alice sorts these selected positions in non-decreasing order, those selected characters become
That puts 0s exactly into the wrong prefix positions and 1s exactly into the wrong suffix positions. Every other position was already correct, so the whole string becomes sorted after this one move.
This completely kills the game:
The only edge case to watch is that if there are no wrong positions, we print Bob. Otherwise, there is at least one wrong 1 in the prefix and one wrong 0 in the suffix, so the move has size at least and strictly modifies the string.
The algorithm is:
Bob; otherwise print Alice and the list.Complexity is per test case, and memory for the output indices. Across all test cases, this is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
string s;
cin >> n >> s;
int zeros = 0;
for (char c : s) zeros += (c == '0');
vector<int> ans;
for (int i = 0; i < zeros; i++) {
if (s[i] == '1') ans.push_back(i + 1);
}
for (int i = zeros; i < n; i++) {
if (s[i] == '0') ans.push_back(i + 1);
}
if (ans.empty()) {
cout << "Bob\n";
} else {
cout << "Alice\n";
cout << ans.size() << '\n';
for (int idx : ans) cout << idx << ' ';
cout << '\n';
}
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
string s;
cin >> n >> s;
int zeros = 0;
for (char c : s) zeros += (c == '0');
vector<int> ans;
for (int i = 0; i < zeros; i++) {
if (s[i] == '1') ans.push_back(i + 1);
}
for (int i = zeros; i < n; i++) {
if (s[i] == '0') ans.push_back(i + 1);
}
if (ans.empty()) {
cout << "Bob\n";
} else {
cout << "Alice\n";
cout << ans.size() << '\n';
for (int idx : ans) cout << idx << ' ';
cout << '\n';
}
}
}