比赛 USACO银组重赛hhh 评测结果 AAAAAAAAAA
题目名称 Swapity Swapity Swap 最终得分 100
用户昵称 梦那边的美好ET 运行时间 0.162 s
代码语言 C++ 内存使用 15.18 MiB
提交时间 2020-03-02 11:28:01
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 100010 
using namespace std;
int n,m,k,a1,a2,f[maxn],g[maxn],ans[maxn],d[maxn],ld;
int main(){
	freopen("usaco_Feb_swap.in","r",stdin);
	freopen("usaco_Feb_swap.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)f[i]=i;
	while(m--){
		scanf("%d%d",&a1,&a2);
		for(int l=a1,r=a2;l<r;l++,r--)swap(f[l],f[r]);
	}
	for(int i=1;i<=n;i++)g[f[i]]=i;
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){
		if(f[i])continue;
		a1=g[i];ld=0;d[ld]=i;
		while(a1!=i)d[++ld]=a1,a1=g[a1];
		a1=g[i];a2=k%(ld+1);
		f[i]=d[a2];
		if(ld!=0)for(int j=1;a1!=i;j++,a1=g[a1])f[a1]=d[(j+a2)%(ld+1)];
	}
	for(int i=1;i<=n;i++)ans[f[i]]=i;
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}