记录编号	590967	评测结果	AAAAAAAAAA
题目名称	[USACO20 Feb Silver]Swapity Swapity Swap	最终得分	100
用户昵称	Untitled	是否通过	通过
代码语言	C++	运行时间	0.204 s
提交时间	2024-07-14 15:05:29	内存使用	4.77 MiB

#include <bits/stdc++.h>
using namespace std;

int const N=100010;
int n,m,k,x[N],y[N],nxt[N],f[N],s[N];//ans[N];
bool d[N];

struct node{
    int i,u;
} ans[N];

bool cmp(node a,node b){
    return a.u<b.u;
}

void init(int x){
    for (int i=1;i<=x;i++) f[i]=i,s[i]=1;
    return;
}

int find(int x){
    if (f[x]==x) return x;
    return f[x]=find(f[x]);
}

void union_set(int x,int y){
    int xr=find(x),yr=find(y);
    if (xr==yr) return;
    f[xr]=yr,s[yr]+=s[xr];
    return;
}

int main(){
    freopen("usaco_Feb_swap.in","r",stdin);
    freopen("usaco_Feb_swap.out","w",stdout);
    
    int l,r,mid,tmp;
    scanf("%d %d %d",&n,&m,&k);
    for (int i=1;i<=n;i++) x[i]=i,y[i]=i;
    for (int i=1;i<=m;i++){
        scanf("%d %d",&l,&r);
        mid=(l+r)>>1;
        for (int j=l;j<=mid;j++){
            swap(y[j],y[r-j+l]);
        }
    }
    init(n);
    for (int i=1;i<=n;i++){
        nxt[y[i]]=i;
        union_set(i,y[i]);
    }
//    for (int i=1;i<=n;i++) printf("%d ",nxt[i]);
//    printf("\n");
    int p,u;
    for (int i=1;i<=n;i++){
        r=find(i);
        if (!d[i]){
            p=k%s[r];
            u=i;
            for (int j=1;j<=p;j++) u=nxt[u];
            ans[i].u=u,ans[i].i=i;;
            for (int v=nxt[i];v!=i;v=nxt[v]) u=nxt[u],ans[v].u=u,ans[v].i=v,d[v]=1;
            d[i]=1;
        }
    }
    sort(ans+1,ans+n+1,cmp);
    for (int i=1;i<=n;i++) printf("%d\n",ans[i].i);
    
    return 0;
}