Cod sursa(job #1559784)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 31 decembrie 2015 15:50:55
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 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 - 1];
int head[MAX_N];

struct HeapKey
{
    int fn;
    int color;
    int priority;

    HeapKey () {}
    HeapKey (const int &E, const int &C, const int &P) : fn(E), color(C), priority(P) {}
};

struct cmp
{
    __inline__ __attribute__((always_inline)) __attribute__((optimize("-O3"))) bool operator () ( const HeapKey &A, const HeapKey &B )
    {
        return A.priority < B.priority;
    }
};

priority_queue < HeapKey, vector <HeapKey>, cmp> Heap;

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 ( int i = 0; i < N; ++i )
        head[i] = NIL;

    for ( register int i = 1; i <= N; ++i )
    {
        if ( A > B )
        {
            st = B;
            fn = A;
        }
        else
        {
            st = A;
            fn = B;
        }

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

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

    Heap.push( HeapKey( N, 0, -1 ) );
    for ( register int i = 1; i < N; ++i )
    {
        for ( int j = head[i]; j != NIL; j = l[j].next )
            Heap.push( HeapKey( l[j].fn, l[j].color, j ) );

        while ( Heap.top().fn < i )
            Heap.pop();

        writeInteger( Heap.top().color );
    }

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