QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546331#7738. Equivalent RewritingAbclRE 0ms0kbC++141.7kb2024-09-03 23:23:012024-09-03 23:23:02

Judging History

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

  • [2024-09-03 23:23:02]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-03 23:23:01]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N=100005;
//拓扑序
int n,m;
int last[N];//最后一次出现
set<int> p[N];//第p次修改的下标
bool f[N];//和上一个是否有连边
//为什么只需要记录两个相邻的操作有没有边呢
//其实相当于构造 假设有操作 x y z
// 操作 x y 相邻 ; z在后面某一个位置 x与 z没有连边 这意味x可以放在z后边
// x放在z后边就相当于在y后边 不会结果有不同的影响 
//所以只需要考虑相邻的两边有没有连边就能进行交换
void solve(){
	 scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)
		p[i].clear();
	memset(last,0,sizeof(last));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){
		int b;scanf("%d", &b);
		for(int j=1,x;j<=b;j++){
			scanf("%d", &x);
			last[x]=i;//这个下标最后一次出现的操作数
			p[i].insert(x);
		}
	}
	//有没有连边
	//有连边就是现在不是最后一次出现 和最后一次出现进行连边
	for(int i=1;i<=m;i++){
		if(last[i]>1&&p[ last[i] - 1 ].count(i)){
			f[last[i]]=true;
		}
	}
	int ans=0;
	for(int i=2;i<=n;i++){
		if(!f[i]){
			ans=i;break;
		}
	}
	if (ans ) {
        printf("Yes\n");
        for (int i = 1; i <= n; i++) {
            if (i == ans - 1) printf("%d", ans);
            else if (i == ans) printf("%d", ans - 1);
            else printf("%d", i);
            printf("%c", "\n "[i < n]);
        }
    } 
	else {
        printf("No\n");
    }
	return;
}
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int T_case=1;
	//cin>>T_case;
	while(T_case--){
		solve();
	}
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

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:


result: