Cod sursa(job #2462071)

Utilizator StanCatalinStanCatalin StanCatalin Data 26 septembrie 2019 18:39:27
Problema Curcubeu Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
/*#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <bitset>
using namespace std;

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

const int dim = 1000010;
bitset <dim> am_cul;

int n,parent[dim],ans[dim],a[dim],b[dim],c[dim],start[dim],cate[dim];

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

int Next(int x)
{
    int rx = Find(x);
    return (start[rx] + cate[rx]);
}

void Union(int x,int y)
{
    int rx = Find(x);
    int ry = Find(y);

    parent[rx] = ry;
    cate[ry] += cate[rx];
    start[ry] = min(start[ry] , start[rx]);
}

int main()
{
    int i,j;
    in >> n >> a[1] >> b[1] >> c[1];
    for (i=1; i<n; i++)
    {
        parent[i] = i;
        cate[i] = 1;
        start[i] = i;
    }
    int a_nou,b_nou,c_nou;
    for (i=2; i<=n-1; i++)
    {
        a[i] = (1LL*a[i-1]*i)%n;
        b[i] = (1LL*b[i-1]*i)%n;
        c[i] = (1LL*c[i-1]*i)%n;
    }

    int st,dr;


    int x;
    for (i=n-1; i>= 1; i--)
    {
        st = min(a[i],b[i]);
        dr = max(a[i],b[i]);
        x = st;
        if (am_cul[x] == 1)
        {
            x = Find(x);
        }

        while (x <= dr)
        {
            am_cul[x] = 1;
            ans[x] = c[i];

            if (x > 1 && am_cul[x-1])
            {
                Union(x-1,x);
            }
            if (x < n-1 && am_cul[x+1])
            {
                Union(x,x+1);
            }
            x = Next(x);
        }

    }
    for (i=1; i<=n-1; i++)
    {
        out << ans[i] << "\n";
    }
    return 0;
}*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

const int dim = 1000001;

int n,parent[dim],ans[dim],a[dim],b[dim],c[dim];

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

int main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    int i,j;
    scanf("%d %d %d %d", &n, &a[1], &b[1], &c[1]);
    for (i=1; i<=n; i++)
    {
        parent[i] = i;
    }
    int a_nou,b_nou,c_nou;
    for (i=2; i<=n-1; i++)
    {
        a[i] = (1LL*a[i-1]*i)%n;
        b[i] = (1LL*b[i-1]*i)%n;
        c[i] = (1LL*c[i-1]*i)%n;
    }

    int st,dr;


    for (i=n-1; i>= 1; i--)
    {
        st = min(a[i],b[i]);
        dr = max(a[i],b[i]);
        for (j=Find(st); j<=dr; j = Find(j))
        {
            ans[j] = c[i];
            parent[j] = j+1;
        }
    }
    for (i=1; i<=n-1; i++)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}