Cod sursa(job #1170295)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 13 aprilie 2014 01:17:49
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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 v[maxn],rightb[maxn],q[maxn];

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)
       rightb[i] = i;

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

        int maxv = r,t = 0;

        for (int j=l; j<=r;)
        {
            if (!v[j])
            {
                v[j] = c[i];
                q[++t] = j;
                ++j;
            }
            else
            {
                rightb[j] = max (rightb[j],r);
                maxv = rightb[j];
                j = rightb[j]+1;
            }
        }

        for (int j=1; j<=t; ++j)
        {
            rightb[q[j]] = max (rightb[q[j]],maxv);
        }
    }

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