Cod sursa(job #1170292)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 13 aprilie 2014 01:12:07
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>

#define maxn 1000001

using namespace std;

ifstream fin ("curcubeu.in");
ofstream fout ("curcubeu.out");

int a[maxn],b[maxn],c[maxn],n,l,r;
int depth[maxn],father[maxn],v[maxn],rightb[maxn];

int parent (int x)
{
    if (father[x])
    {
        return father[x] = parent(father[x]);
    }
    return x;
}

void unite (int x, int y)
{
    x = parent (x);
    y = parent (y);

    if (x != y)
    {
        if (depth[x] < depth[y])
        {
            father[x] = y;;
        }
        else
        {
            father[y] = x;
            if (depth[x] == depth[y])
                depth[x]++;
            rightb[x] = rightb[y];
        }
    }
}

int main()
{
    freopen ("curcubeu.out","w",stdout);

    fin>>n;
    --n;

    fin>>a[1]>>b[1]>>c[1];

    for (int i=2; i<=n; ++i)
    {
        a[i] = (1LL*a[i-1]*i)%(n+1);
        b[i] = (1LL*b[i-1]*i)%(n+1);
        c[i] = (1LL*c[i-1]*i)%(n+1);
    }

    for (int i=1; i<=n; ++i)
        depth[i] = 1,rightb[i] = i;

    for (int i=n; i>=1; --i)
    {
        l = min (a[i],b[i]);
        r = max (a[i],b[i]);

        for (int j=l; j<=r;)
        {
            if (v[j-1])
            {
                unite(j-1,j);
            }

            if (!v[j])
            {
                v[j] = c[i];
                ++j;
            }
            else
            {
                int x = parent(j);
                j = rightb[x]+1;
            }
        }
    }

    for (int i=1; i<=n; ++i)
    {
        printf ("%d\n",v[i]);
    }
}