记录编号	550056	评测结果	AAAAAAAAAA
题目名称	[USACO20 Feb Silver]Swapity Swapity Swap	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2020-03-02 11:27:39	内存使用	15.18 MiB

#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;
}