CF1798B题解

ncwzdlsd · 2023-10-23 14:22:35 · 题解

设编号为 i 的人最后买彩票在 lst_i 天，容易想到，把中奖者的中奖日期安排在他买彩票的最后一天是一种合理的方案。

用 day_i 表示每一天中奖者的编号，如果有一天找不到满足条件的中奖者，则不存在方案。

代码如下：

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

const int maxn=50005;
int lst[maxn],day[maxn];

void solve()
{
    int m=read();
    int mxid=1;
    memset(lst,0,sizeof lst),memset(day,0,sizeof day);
    for(int i=1;i<=m;i++)
    {
        int n=read();
        for(int j=1;j<=n;j++)
        {
            int a=read();lst[a]=i;
            mxid=max(mxid,a);
        }
    }
    for(int i=1;i<=mxid;i++) if(lst[i]) day[lst[i]]=i;
    bool flag=1;
    for(int i=1;i<=m;i++) if(!day[i]){flag=0;break;}
    if(flag) for(int i=1;i<=m;i++) cout<<day[i]<<' ';
    else cout<<"-1";
    cout<<'\n';
}

int main()
{
    int t=read();
    while(t--) solve();
    return 0;
}