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.
Do not simulate every person from cell from scratch. That is , and the time limit will bonk it instantly.
Keep one variable: where a person would end after the already-processed prefix under the current black cells.
Command A is stable: if it moves to , painting that cell black does not change the result of A later. Command B is not stable: it lands on a white cell, then you immediately make that exact cell black.
So for B, first move to the next white cell, paint it, then advance again to the next white cell for the maintained future state.
Maintain get(x) = smallest white cell using DSU/path-compression over black cells: if is black, jump to get(x+1). Output all black keys sorted.
The big false assumption is: “person is just person plus one more command.” Nope. Everyone restarts at cell , and newly painted cells can change future B jumps.
But we can still process the string left to right with one maintained position.
The right invariant
After processing the first people, let cur be the cell where a new person would stand after executing the first commands using the current black set.
Initially, before any commands, cur = 1.
Now process the next command.
If the command is A
The person moves from cur to:
Then that cell is painted black. But A does not care whether the destination is black or white. So for future people, after this prefix, the position is still cur+1.
So:
cur = cur + 1
paint cur blackIf the command is B
The person moves to the first white cell strictly after cur. Call it .
Then is painted black.
For future people, when they execute this same B from cur, they can no longer land on , because we just made it black. So the maintained cur must become the next white cell at or after after the insertion.
So:
y = first white cell >= cur + 1
paint y black
cur = first white cell >= yThat second update is the whole trick. Tiny line, annoying if missed.
Why painting the endpoint does not break earlier commands
The newly painted endpoint is after the position reached by the previous prefix. Earlier commands in the prefix already ended at cells no larger than that previous prefix position, so none of their B jumps could have been landing on this new endpoint. Only the newest command can need adjustment, and only when it is B.
That makes the one-variable invariant valid.
Finding the next white cell
We need dynamic operations:
Only cells can ever become black, so do not build an array of size . That would be industrial-grade nonsense.
Use DSU-style path compression on black cells.
Let get(x) return the smallest white cell .
get(x) = x.For every black cell , store:
Then:
get(x):
if x is white: return x
parent[x] = get(parent[x])
return parent[x]The implementation below uses an ordered map. Its keys are exactly the black cells, so output is automatically sorted.
Complexity
There are insertions and next-white queries. With path compression and ordered-map lookups, the complexity is:
per test case, across the total input size. Easily fine.
#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, m;
string s;
cin >> n >> m >> s;
map<ll, ll> parent; // keys are exactly the black cells
vector<ll> path;
auto get = [&](ll x) {
path.clear();
while (true) {
auto it = parent.find(x);
if (it == parent.end()) break;
path.push_back(x);
x = it->second;
}
for (ll v : path) parent[v] = x;
return x;
};
auto addBlack = [&](ll x) {
if (parent.find(x) != parent.end()) return;
ll to = get(x + 1);
parent.emplace(x, to);
};
for (int i = 0; i < m; i++) {
ll x;
cin >> x;
addBlack(x);
}
ll cur = 1;
for (char c : s) {
if (c == 'A') {
++cur;
addBlack(cur);
} else {
cur = get(cur + 1);
addBlack(cur);
cur = get(cur);
}
}
cout << parent.size() << '\n';
for (auto [x, _] : parent) cout << x << ' ';
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, m;
string s;
cin >> n >> m >> s;
map<ll, ll> parent; // keys are exactly the black cells
vector<ll> path;
auto get = [&](ll x) {
path.clear();
while (true) {
auto it = parent.find(x);
if (it == parent.end()) break;
path.push_back(x);
x = it->second;
}
for (ll v : path) parent[v] = x;
return x;
};
auto addBlack = [&](ll x) {
if (parent.find(x) != parent.end()) return;
ll to = get(x + 1);
parent.emplace(x, to);
};
for (int i = 0; i < m; i++) {
ll x;
cin >> x;
addBlack(x);
}
ll cur = 1;
for (char c : s) {
if (c == 'A') {
++cur;
addBlack(cur);
} else {
cur = get(cur + 1);
addBlack(cur);
cur = get(cur);
}
}
cout << parent.size() << '\n';
for (auto [x, _] : parent) cout << x << ' ';
cout << '\n';
}
}