Pagini recente » Cod sursa (job #64139) | Cod sursa (job #407108) | Cod sursa (job #3168177) | Cod sursa (job #1116210) | Cod sursa (job #349060)
Cod sursa(job #349060)
# include <stdio.h>
# include <stdlib.h>
typedef struct INTERVAL
{
long int a,b,c;
};
const long int MAXN=1000000;
INTERVAL interval[MAXN+1];
long int n,col[MAXN+1],set[MAXN+1],size[MAXN+1];
void citire()
{
long int a,c,b;
FILE *f=fopen("curcubeu.in","r");
fscanf(f,"%ld%ld%ld%ld",&n,&a,&b,&c);
long int i=1;
do
{
if (a<b)
{
interval[i].a=a;
interval[i].b=b;
}
else
{
interval[i].b=a;
interval[i].a=b;
}
interval[i].c=c;
i++;
a=(a*i)%n;
b=(b*i)%n;
c=(c*i)%n;
}
while (i<=n-1);
}
long int get_set(long int j)
{
long int i=j;
while (set[i]!=i) i=set[i];
set[j]=i;
return i;
}
long int merge_set(long int a, long int b)
{
if (a<b)
{
set[b]=a;
size[a]+=b;
}
else
{
set[a]=b;
size[b]+=a;
}
}
void paint(long int a, long int b, long int c)
{
long int i,pr,act;
for (i=a;i<=b;)
if (col[i]==0)
{
col[i]=c;
if (i>1)
{
pr=get_set(i-1);
merge_set(i,pr);
}
i++;
}
else
{
if (i>a)
{
pr=get_set(i-1);
act=get_set(i);
if (pr!=act) merge_set(pr,act);
i=get_set(i)+size[get_set(i)];
}
else
{
i=get_set(i)+size[get_set(i)];
}
}
}
void calculeaza()
{
long int i;
for (i=1;i<=n-1;i++) {set[i]=i;size[i]=1;}
for (i=n-1;i>=1;i--)
paint(interval[i].a,interval[i].b,interval[i].c);
}
void scrie()
{
FILE *g=fopen("curcubeu.out","w");
long int i;
for (i=1;i<=n-1;i++)
fprintf(g,"%ld\n",col[i]);
fclose(g);
}
int main()
{
citire();
calculeaza();
scrie();
return 0;
}