神奇模拟题。最直接的做法就是每个石头暴力向下滚，有 \(60\) 分。但是大样例跑了 \(15s\)。稍微观察一下，会发现很多次循环都是在重复向下走到一格空位上，于是考虑优化：用 set 维护每一列的那些位置有障碍（包括石头），每次直接 lower_bound 跳到下一个位置，会快很多，大样例 \(1.7s\)。赛时就写的这个，但还是过不去的。因为反复横跳就会将其卡至 \(O(nr \log r)\)。
我们发现 \(c\) 是很小的，也就意味着会有很多次都是从同一列向下滚。观察发现：同一列的滚动路径只会有后面连续的一段会被改变。也就是说假如这列第一个球的路径是 \(p_1,p_2...p_x\) ，那么下一个小球的路径的前半段一定与当前小球相同。因为假设有一个位置 \(y\) 使得 \(p_y\) 被覆盖而 \(p_{y+1}\) 没有被覆盖，那么小球沿着滚动路径一定能放下滚去覆盖 \(p_{y+1}\)，与假设矛盾。
因此，我们直接维护从当前列开始扔，到第 \(x\) 行是在第几列。因为有可能会有一些小球会把当前位置占掉，所以我们在进行操作前要先将被占的位置撤销，找到一个空列再下落。这样时间复杂度就均摊下来了，为 \(O(rc^2)\)。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int r,c;
char a[30005][35];
int n,x,vis[30005][35];
int h[35][300005],pos[34];//h[i][j]表示从第i列开始扔，到第j行在哪一列
set<int>s[35];
int main(){
// freopen("kamen.in","r",stdin);
// freopen("kamen.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>r>>c;
for(int i=1;i<=r;++i){
for(int j=1;j<=c;++j){
cin>>a[i][j];
if(a[i][j]=='X')vis[i][j]=1;
}
}
for(int i=1;i<=c;++i)h[i][0]=i;
int q;
cin>>q;
while(q--){
cin>>x;
while(1){
int now=h[x][pos[x]];//pos[x]相当于记录从x列滚到了多少行
if(vis[pos[x]][now])pos[x]--; //先把被占的地方退回
else if(pos[x]==r)break;//到底了
else if(a[pos[x]+1][now]=='X')break;//遇到障碍
else if(!vis[pos[x]+1][now])h[x][++pos[x]]=now;//可以向下走
else if(now-1>=1&&(!vis[pos[x]][now-1])&&(!vis[pos[x]+1][now-1]))h[x][++pos[x]]=now-1;//向左
else if(now+1<=c&&(!vis[pos[x]][now+1])&&(!vis[pos[x]+1][now+1]))h[x][++pos[x]]=now+1;//向右
else break;//走不了了
}
a[pos[x]][h[x][pos[x]]]='O';//更新
vis[pos[x]][h[x][pos[x]]]=1;
}
for(int i=1;i<=r;++i){
for(int j=1;j<=c;++j)cout<<a[i][j];
cout<<'\n';
}
return 0;
}