QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698176 | #7738. Equivalent Rewriting | bessie_goes_moo# | WA | 2ms | 10252kb | C++17 | 2.1kb | 2024-11-01 17:59:00 | 2024-11-01 17:59:01 |
Judging History
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)