/ zzf / 讨论 / 题解 /

疯狂的涂色

#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 条评论

  • 1