- 题解
- 2018-10-18 19:43:18 @
#include <cstdio>
#include <algorithm>
#include <cstring>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Dor(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define N 10000005
#define M 1000005
using namespace std;
int n,m,p,q,stack[N],top=0,fa[M],map[M],l,r,lm,rm;
//普通的并查集会溢出,手写栈
int getf(int x){
int t;
while (fa[x]!=x){
stack[++top]=x;
x=fa[x];
}
t=fa[x];
while (top>0){
x=stack[top--];
fa[x]=t;
}
return t;
}
int main(){
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&q);
For(i,1,n) fa[i]=i;
Dor(i,m,1){
if (m-i+1>n) break;
int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
if (l>r) swap(l,r);
if(i==m){lm=(m*p+q)%n+1;rm=(m*q+p)%n+1;}
else if(l==lm && r==rm) break;//寻找循环节点
for(int j=getf(r);j>l-1;j=getf(j)){
if (!map[j]) map[j]=i;
fa[j]=j-1;//并查集维护
}
}
For(i,1,n) printf("%d\n",map[i]);
fclose(stdin);fclose(stdout);
return 0;
}
4 条评论
-
张鑫杰 LV 4 MOD @ 2018-10-18 19:52:53
ZZF SB
-
2018-10-18 19:47:42@
我是桌桌疯
-
2018-10-18 19:47:23@
啦啦啦
-
2018-10-18 19:46:59@
呵呵
- 1