Cod sursa(job #1861546)

Utilizator silkMarin Dragos silk Data 28 ianuarie 2017 23:32:02
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 1000000
#define DIM 50000
using namespace std;
char buff[DIM+1];
int poz;

FILE* fin = fopen("curcubeu.in","r");
FILE* fout = fopen("curcubeu.out","w");

char is[NMax+1];
int t[2][NMax+1];
int col[NMax+1];
int st[NMax+1];
int dr[NMax+1];
int a[NMax+1];

int Find(int x, int l)
{
    int v,rad=x;

    while(t[l][rad]) rad = t[l][rad];
    while(t[l][x])
    {
        v = t[l][x];
        t[l][x] = rad;
        x = v;
    }
    return rad;
}

void Union(int x, int y, int l)
{
    if(x != y) t[l][x] = y;
}

void write_ch(char ch)
{
    if (poz == DIM){
        fwrite(buff,1,DIM,fout);
        poz=0;
        buff[poz++] = ch;
    } else buff[poz++] = ch;
}

void write_u32(int vu32)
{
    if (vu32 <= 9) {
        write_ch(vu32 + '0');
    } else {
        write_u32(vu32 / 10);
        write_ch(vu32 % 10 + '0');
    }
}

void write_appendix()
{
    fwrite(buff,1,poz,fout);
    fclose(fout);
}

int main(){

    int i,j,p,u,N,A,B,C;

    fscanf(fin,"%d %d %d %d",&N,&A,&B,&C);
    for(i = 2; i <= N; ++i)
    {
        st[i-1] = min(A,B);
        dr[i-1] = max(A,B);
        col[i-1] = C;
        A = (1LL * A * i) % N;
        B = (1LL * B * i) % N;
        C = (1LL * C * i) % N;
    }

    for(i = N-1; i >= 1; --i)
    {
        p = Find(st[i], 1);
        while(is[p]){ ++p; Find(p,1); }

        u = Find(dr[i], 0);
        while(is[u]){ --u; Find(u,0); }

        if(p < N && u > 0 )
        for(j = p; j <= u; ++j)
        {
            is[j] = 1;
            a[j] = col[i];
            Union(j, st[i], 0);
            Union(j, dr[i], 1);
        }
    }

    for(i = 1; i < N; ++i) { write_u32(a[i]); write_ch('\n'); }
    write_appendix();


return 0;
}