正确答案

【题目描述】

小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。

“吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。

外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。这可让小Y与小H犯了难。你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。无解输出-1。

【输入格式】

第一行四个整数n, m, p, q，意义如上描述。

接下来n行，每一行m个字符’N’或’Y’，表示这题这个神犇的答案。

【输出格式】

仅一行，一个长度为m的字符串或是-1。

【样例输入】

2 2 2 0

【样例输出】

【数据范围】

30% : n <= 100.

60% : n <= 5000 , m <= 100.

100% : 1 <= n <= 30000 , 1 <= m <= 500. 0 <= p , q 且 p + q <= n.

/*
  直接map模拟，一开始p=q=0的情况判错了，以为无解
  而且由于输入用的cin，TLE成SB了，以后字符串不要用cin。
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<map>
#define N 30010
#define M 510
using namespace std;
string ans[N];char ss[M];
map<string,int> mp;
int n,m,p,q;
void work1(){
    int A[510]={0};bool ok=false;
    while(1){
        string now="",fan="";
        for(int i=0;i<m;i++)
            if(!A[i])now+="N",fan+="Y";
            else now+="Y",fan+="N";
        if(!mp[now]&&!mp[fan]){
            cout<<now;ok=true;break;
        }
        A[m-1]++;bool gogogo=false;
        for(int i=m-1;i>=0;i--){
            if(A[i]==2){
                if(i==0)break;
                A[i]=0;A[i-1]++;
            }
            else {
                gogogo=true;
                break;
            }
        }
        if(!gogogo)break;
    }
    if(!ok)printf("-1");
}
void work2(){
    bool ok=false;
    for(int i=1;i<=n;i++){
        int num=mp[ans[i]];
        if(num!=p)continue;
        string fan="";
        for(int j=0;j<m;j++)
            if(ans[i][j]=='N')fan+="Y";
            else fan+="N";
        if(!mp[fan]){
            cout<<ans[i];ok=true;break;
        }
    }
    if(!ok)printf("-1");
}
void work3(){
    bool ok=false;
    for(int i=1;i<=n;i++){
        int num=mp[ans[i]];
        if(num!=q)continue;
        string fan="";
        for(int j=0;j<m;j++)
            if(ans[i][j]=='N')fan+="Y";
            else fan+="N";
        if(!mp[fan]){
            cout<<fan;ok=true;break;
        }
    }
    if(!ok)printf("-1");
}
void work4(){
    bool ok=false;
    for(int i=1;i<=n;i++){
        int num=mp[ans[i]];
        if(num!=p)continue;
        string fan="";
        for(int j=0;j<m;j++)
            if(ans[i][j]=='N')fan+="Y";
            else fan+="N";
        if(mp[fan]==q){
            cout<<ans[i];ok=true;break;
        }
    }
    if(!ok)printf("-1");
}
int main(){
    //freopen("answer.in","r",stdin);
    //freopen("answer.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&p,&q);
    for(int i=1;i<=n;i++){
        scanf("%s",ss);
        for(int j=0;j<m;j++)
            ans[i]+=ss[j];
        mp[ans[i]]++;
    }
    sort(ans+1,ans+n+1);
    if(p==0&&q==0)work1();
    if(p&&q==0)work2();
    if(p==0&&q)work3();
    if(p&&q)work4();
    return 0;
}