水题。
发现根据限制 \(M_{i,j}=M_{j,i}\) 可以知道除了主对角线上的点，其他的点都是成对出现的。也就是说如果有一条要求的 \(a_i\) 为奇数，那么至少有一个 \(c_i\) 在主对角线上。
记 \(S=\sum\limits_{i=1}^{k} (a_i\equiv 1\pmod 2)\)，即有 \(S\) 个要求中 \(a_i\) 为奇数。主对角线上只有 \(n\) 个点，所以若 \(S>n\) 则无解。
如果 \(S=n\) 很好处理，但如果 \(S<n\)，说明主对角线上还需要放别的数，而且要一次性放入两个。
我们按字典序从小到大枚举字符，只处理 \((i,j)|i\leq j\) ，也就是主对角线及上方的点。
对于主对角线特别考虑，维护一个栈，从栈顶到栈底从小到大。里面放入现在剩余未填个数为奇数的字符，每次比较栈顶字符 \(a\) 和当前的枚举字符 \(b\)，设栈的大小为 \(cnt\)，当前位置为 \((i,i)\)：
如果 \(b<a\) 则说明将 \(b\) 填在此处比将 \(a\) 填在此处更优，但同时需要保证 \((i-1)+(cnt+2)\leq n\)，因为主对角线上已经填过 \(i-1\) 个数，如果将 \(b\) 填在这里，就说明在第 \(i\sim n\) 行的主对角线上要填 \(cnt+2\) 个数。所以如果这个值大于 \(n\) 就会不合法。
对于其他点直接顺次放，一种字符一定是连续的，每一行用 vector 维护连续的字符段。总共 \(n\) 行只会有 \(n+|\Sigma|\) 个连续字符段，其中 \(|\Sigma|\) 表示字符集大小。
输出答案时直接遍历，一行最多只会有 \(|\Sigma|\) 连续的字符段，并且均摊 \(O(1)\)。
总时间复杂度为 \(O(np)\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=3e4+10;
int n,k,t[26],q[30],cnt,p,pos[60],h[MAXN];
struct node{int l,r,num;};
vector < node > v[MAXN];
inline char ANS(int x,int y)
{
if(x>y) return ANS(y,x);
if(x==y) return h[x]+65;
for(node z:v[x]) if(z.l<=y&&z.r>=y) return z.num+65;
return 0;
}
int main()
{
#ifdef ONLINE_JUDGE
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
#endif
cin>>n>>k;
for(register int i=1;i<=k;++i){char c;int a;cin>>c>>a;t[c-65]=a;}
//逆序，这样从栈顶到栈底从小到大；t[i]/=2 因为只考虑主对角线及上方
for(register int i=25;i>=0;--i){if(t[i]&1) q[++cnt]=i;t[i]/=2;}
if(cnt>n){cout<<"IMPOSSIBLE\n";return 0;}
cin>>p;for(register int i=1;i<=p;++i) cin>>pos[i];
//cur 是枚举元素
for(register int i=1,cur=0;i<=n;++i)
{
while(!t[cur]) ++cur;
//这里还要在栈顶加入 cur，因为这一行只填了一个，它变成了还剩奇数个未填
if((cur<q[cnt]||!cnt)&&i+cnt+1<=n) h[i]=cur,t[cur]-=1,q[++cnt]=cur;
else h[i]=q[cnt--];
for(int l=i+1,r;l<=n;l=r+1)
{
while(!t[cur]) ++cur;
r=min(n,l+t[cur]-1);
v[i].push_back({l,r,cur});
t[cur]-=(r-l+1);
}
for(register int j=1;j<=p;++j) cout<<ANS(i,pos[j]);
cout<<'\n';
}
return 0;
}