Cod sursa(job #1559794)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 31 decembrie 2015 16:13:06
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int BUFF_SIZE = 7000000;
const int NIL = -1;

char buff[BUFF_SIZE];
int ptr = 0;

__inline__ __attribute__((always_inline)) __attribute__((optimize("-O3"))) void writeInteger(int x)
{
    int q;
    int st = ptr, fn = ptr;

    do
    {
        q = x / 10;
        buff[fn++] = x - (q << 1) - (q << 3) + '0';
        x = q;
    } while ( x > 0 );

    ptr = fn;

    while ( st < fn )
        swap( buff[st++], buff[--fn] );

    buff[ptr++] = '\n';
}

struct Lista
{
    int fn;
    int color;
    int next;
};

Lista l[MAX_N];
int head[MAX_N];

int H[MAX_N];
int heapSize;

void downHeap( int X )
{
    bool changed;
    int leftSon, rightSon;
    int best;

    do
    {
        changed = 0;
        best = X;
        leftSon = 2 * X + 1;
        rightSon = 2 * X + 2;

        if ( leftSon < heapSize && H[leftSon] > H[best] )
            best = leftSon;

        if ( rightSon < heapSize && H[rightSon] > H[best] )
            best = rightSon;

        if ( best != X )
        {
            changed = 1;
            swap( H[best], H[X] );
            X = best;
        }
    } while ( changed );
}

void upHeap( int X )
{
    int father = X / 2;

    while ( ( X > 0 ) && ( H[father] < H[X] ) )
    {
        swap( H[father], H[X] );
        X = father;
        father = X / 2;
    }
}

int main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    int N;
    int A, B, C;
    int st, fn;
    unsigned long long tmp;

    scanf("%d%d%d%d", &N, &A, &B, &C);
    fclose(stdin);

    for ( register int i = 2; i < N; ++i )
        head[i] = NIL;

    l[0].color = 0;
    l[0].fn = N;
    l[0].next = NIL;
    head[1] = 0;
    for ( register int i = 1; i < N; ++i )
    {
        if ( A > B )
        {
            st = B;
            fn = A;
        }
        else
        {
            st = A;
            fn = B;
        }

        l[i].color = C;
        l[i].fn = fn;
        l[i].next = head[st];
        head[st] = i;

        tmp = 1ULL * A * (1 + i);
        A = tmp - tmp / N * N;
        tmp = 1ULL * B * (1 + i);
        B = tmp - tmp / N * N;
        tmp = 1ULL * C * (1 + i);
        C = tmp - tmp / N * N;
    }

    heapSize = 0;
    for ( register int i = 1; i < N; ++i )
    {
        for ( int j = head[i]; j != NIL; j = l[j].next )
        {
            H[heapSize] = j;
            upHeap( heapSize );
            heapSize++;
        }

        while ( l[H[0]].fn < i )
        {
            H[0] = H[--heapSize];
            downHeap( 0 );
        }

        writeInteger( l[H[0]].color );
    }

    fwrite( buff, 1, ptr, stdout );
    fclose(stdout);
    return 0;
}