Cod sursa(job #2006349)

Utilizator cipri321Marin Ciprian cipri321 Data 29 iulie 2017 15:27:36
Problema Curcubeu Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <cstdio>
#define DIM 1000001
using namespace std;
ifstream fi("curcubeu.in");
int n,A[DIM],B[DIM],C[DIM],CUL[DIM],D[DIM],P[DIM];
int radacina(int a)
{
    if(P[a]==0)
        return a;
    P[a]=radacina(P[a]);
    return P[a];
}
void reuneste(int a,int b)
{
    int ra=radacina(a),rb=radacina(b);
    if(ra!=rb)
    {
        D[ra]+=D[rb];
        P[rb]=ra;
    }
}
void smecherie(int st,int dr,int c)
{
    for(int i=st;i<=dr;i+=D[i])
    {
        if(CUL[i]==-1)
        {
            CUL[i]=c;
            if(i>1 && CUL[i-1]!=-1)
                reuneste(i-1,i);
            if(i<n && CUL[i+1]!=-1)
                reuneste(i,i+1);
        }
        i=radacina(i);
    }
}
FILE *_fout;
int _out_loc; char _out_buff[50000];

void write_init(const char* name) // Apelaţi această funcţie la începutul funcţiei <main>
{
    _fout = fopen(name, "w");
    _out_loc = 0;
}

void write_ch(char ch) // Apelaţi această funcţie pentru a scrie un caracter (cum ar fi ' ' sau '\n')
{
    if (_out_loc == 50000) {
        fwrite(_out_buff, 1, 50000, _fout);
        _out_loc = 0;
        _out_buff[_out_loc++] = ch;
    } else {
        _out_buff[_out_loc++] = ch;
    }
}

void write_u32(unsigned int vu32) // Apelaţi această funcţie pentru a scrie un număr ce se încadrează în categoria <unsigned int>
{
    if (vu32 <= 9) {
        write_ch(vu32 + '0');
    } else {
        write_u32(vu32 / 10);
        write_ch(vu32 % 10 + '0');
    }
}

void write_appendix() // ###! ATENŢIE, Apelaţi această funcţie la finalul prgramului. Altfel, fisierul outpt NU VA CONŢINE ÎN ÎNTREGIME ceea ce doriţi!
{
    fwrite(_out_buff, 1, _out_loc, _fout);
    fclose(_fout);
}
int main()
{
    write_init("curcubeu.out");
    fi>>n>>A[1]>>B[1]>>C[1];
    for(int i=1;i<=n-1;i++)
        D[i]=1,CUL[i]=-1;
    for(int i=2;i<=n-1;i++)
    {
        A[i]=(1LL*A[i-1]*i)%n;
        C[i]=(1LL*C[i-1]*i)%n;
        B[i]=(1LL*B[i-1]*i)%n;
    }
    for(int i=n-1;i>=1;i--)
        smecherie(min(A[i],B[i]),max(A[i],B[i]),C[i]);
    for(int i=1;i<n;i++)
    {
        write_u32(CUL[i]);
        write_ch('\n');
    }
    write_appendix();
    fi.close();
    return 0;
}