QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698176#7738. Equivalent Rewritingbessie_goes_moo#WA 2ms10252kbC++172.1kb2024-11-01 17:59:002024-11-01 17:59:01

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 17:59:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10252kb
  • [2024-11-01 17:59:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int read(){
    int red=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') red=red*10+ch-48,ch=getchar();
    return red*f;
}
const int N=1e5+5;
int T,n,m,p[N];
vector<int>A[N],B[N];
int vis[N],Min[N],Up[N];
int st[N],top;
int ans[N];
void clear(){
    for(int i=1;i<=n;i++) Up[i]=0;
}
int main(){
    T=read();
    while(T--){
        clear();m=read(),n=read();
        for(int i=1;i<=m;i++){
            p[i]=read();
            B[i].resize(p[i]);B[i].clear();
            A[i].resize(p[i]);A[i].clear();
            for(int j=0;j<p[i];j++) B[i][j]=read();
        }
        for(int i=m;i;i--){
            Min[i]=m+1;
            for(int j=0;j<p[i];j++){
                if(!vis[B[i][j]]){
                    A[i][j]=1;
                    vis[B[i][j]]=i;
                }
                else{
                    Min[i]=min(Min[i],vis[B[i][j]]);
                    if(!Up[B[i][j]]) Up[B[i][j]]=i;
                }
            }
        }
        bool ok=0;
        st[top=1]=1;
        for(int i=2;i<=m;i++){
            int Up_=0;
            for(int j=0;j<p[i];j++) 
                if(vis[B[i][j]]==i)
                    Up_=max(Up_,Up[B[i][j]]);
            if(!Up_){
                ok=1;
                ans[1]=i;
                for(int k=2;k<=i;k++) ans[k]=k-1;
                for(int k=i+2;k<=m;k++) ans[k]=k;
                printf("Yes\n");
                for(int k=1;k<m;k++) printf("%d ",ans[k]);
                printf("%d\n",ans[m]);
                break;
            }
            int id=upper_bound(st+1,st+1+top,Up_)-st;
            if(id<=top&&Min[st[id]]<i){
                for(int k=1;k<=m;k++) ans[k]=k;
                swap(ans[st[id]],ans[i]);
                printf("Yes\n");
                for(int k=1;k<m;k++) printf("%d ",ans[k]);
                printf("%d\n",ans[m]);
                break;
            }
            while(top&&Min[st[top]]>=Min[i]) top--;
            st[++top]=i;
        }
        if(!ok) printf("No\n");
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 10000kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
3 1 2
No
No

result:

ok OK. (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 10252kb

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:

Yes
2 1 0 4 5 6 7 8 9 10

result:

wrong answer Integer parameter [name=q_i] equals to 0, violates the range [1, 10] (test case 1)