Cod sursa(job #2708166)

Utilizator AACthAirinei Andrei Cristian AACth Data 18 februarie 2021 13:05:37
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb

#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 1000000
#define DIM 50000
using namespace std;
char buff[DIM+1];
int poz;
//merge serveru prost deci testez cu cea mai rapida din statistici
FILE* fin = fopen("curcubeu.in","r");
FILE* fout = fopen("curcubeu.out","w");

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

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

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

void Union(int x, int y)
{
    if(x != y) t[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]);
        while(p <= dr[i])
        {
            if(is[p]) p = Find(++p);
            else{
                a[p] = col[i];
                is[p] = 1;
                Union(p, dr[i]);
                p = Find(++p);
            }
        }
    }

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


return 0;
}