记录编号	270386	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]白雪皑皑	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	1.567 s
提交时间	2016-06-14 19:55:24	内存使用	122.38 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int c[1000015];
int last[1000015];
struct node
{
    int l,r,color;
};
node f[10000100];
int main()
{
    freopen("winter.in","r",stdin);
    freopen("winter.out","w",stdout);
    int n,m,p,q;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    for(int i=1;i<=m;i++)
    {
        int l=(i*p+q)%n+1;
        int r=(i*q+p)%n+1;
        if(l>r) swap(l,r);
        f[i].l=l;f[i].r=r;f[i].color=i;
    }
    for(int i=m;i>=1;i--)
    {
        for(int j=f[i].l;j<=f[i].r;j++)
        {
            if(last[j]==0)
            {
                last[j]=f[i].r;
                c[j]=i;
            }
            else
            {
                if(last[j]>=f[i].r) break;
                else j=last[j];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",c[i]);
    }
    return 0;
}