Cod sursa(job #1170286)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 13 aprilie 2014 00:55:21
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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;
            rightb[y] = max(rightb[x],rightb[y]);
        }
        else
        {
            father[y] = x;
            if (depth[x] == depth[y])
                depth[x]++;
            rightb[x] = max (rightb[x],rightb[y]);
        }
    }
}

int main()
{
    fin>>n;
    --n;

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

    for (int i=2; i<=n; ++i)
    {
        a[i] = (a[i-1]*i)%(n+1);
        b[i] = (b[i-1]*i)%(n+1);
        c[i] = (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])
            {
                v[j] = c[i];
                ++j;
            }
            else
            {
                if (v[j-1])
                {
                    unite(j-1,j);
                }

                int x = parent(j);
                j = rightb[x]+1;
            }
        }
    }

    for (int i=1; i<=n; ++i)
    {
        fout<<v[i]<<"\n";
    }
}