Cod sursa(job #586224)

Utilizator katakunaCazacu Alexandru katakuna Data 30 aprilie 2011 14:10:02
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 4.46 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <set>
using namespace std;

#define Nmax 100010
#define Mmax 50010

#define INF 0x3f3f3f3f

int n, Na, Nb;
int A[Mmax], B[Mmax], T[Nmax], Sol[Nmax];

int H1[Nmax], H2[Nmax], H3[Nmax];
int Poz1[Nmax], Poz3[Nmax];
int Cst[Nmax];
int N1, N2, N3;

void up_heap1 (int p) {

    int t, c = p, aux;
    t = c >> 1;

    while (t && Cst[ H1[t] ] + A[ H1[t] ] > Cst[ H1[c] ] + A[ H1[c] ]) {
        aux = H1[t];
        H1[t] = H1[c];
        H1[c] = aux;

        Poz1[ H1[t] ] = t;
        Poz1[ H1[c] ] = c;

        c = t;
        t = c >> 1;
    }
}

void up_heap3 (int p) {

    int t, c = p, aux;
    t = c >> 1;

    while (t && Cst[ H3[t] ] > Cst[ H3[c] ]) {
        aux = H3[t];
        H3[t] = H3[c];
        H3[c] = aux;

        Poz3[ H3[t] ] = t;
        Poz3[ H3[c] ] = c;

        c = t;
        t = c >> 1;
    }
}

void up_heap2 (int p) {

    int t, c = p, aux;
    t = c >> 1;

    while (t && A[ H2[t] ] > A[ H2[c] ]) {
        aux = H2[t];
        H2[t] = H2[c];
        H2[c] = aux;

        c = t;
        t = c >> 1;
    }
}

void down_heap1 (int p) {

    int t = p, c, aux;
    c = t << 1;

    if (c < N1 && Cst[ H1[c + 1] ] + A[ H1[c + 1] ] < Cst[ H1[c] ] + A[ H1[c] ]) c++;

    while (c <= N1 && Cst[ H1[t] ] + A[ H1[t] ] > Cst[ H1[c] ] + A[ H1[c] ]) {
        aux = H1[t];
        H1[t] = H1[c];
        H1[c] = aux;

        Poz1[ H1[t] ] = t;
        Poz1[ H1[c] ] = c;

        t = c;
        c = t << 1;
        if (c < N1 && Cst[ H1[c + 1] ] + A[ H1[c + 1] ] < Cst[ H1[c] ] + A[ H1[c] ]) c++;
    }
}

void down_heap3 (int p) {

    int t = p, c, aux;
    c = t << 1;

    if (c < N3 && Cst[ H3[c + 1] ] < Cst[ H3[c] ] ) c++;

    while (c <= N3 && Cst[ H3[t] ] > Cst[ H3[c] ]) {
        aux = H3[t];
        H3[t] = H3[c];
        H3[c] = aux;

        Poz3[ H3[t] ] = t;
        Poz3[ H3[c] ] = c;

        t = c;
        c = t << 1;
        if (c < N3 && Cst[ H3[c + 1] ] < Cst[ H3[c] ] ) c++;
    }
}

void down_heap2 (int p) {

    int t = p, c, aux;
    c = t << 1;

    if (c < N2 && A[ H2[c + 1] ] < A[ H2[c] ]) c++;

    while (c <= N2 && A[ H2[t] ] > A[ H2[c] ]) {
        aux = H2[t];
        H2[t] = H2[c];
        H2[c] = aux;

        t = c;
        c = t << 1;
        if (c < N2 && A[ H2[c + 1] ] < A[ H2[c] ]) c++;
    }
}

void rezolva () {

    int i, c1, c2, nod;

    sort (T + 1, T + n + 1);

    N1 = N2 = N3 = 0;
    for (i = 1; i <= Na; i++) {
        H1[++N1] = i; Poz1[i] = N1;
        H3[++N3] = i; Poz3[i] = N3;
        Cst[i] = 0;
        up_heap1 (N1);
        up_heap3 (N3);
    }

    for (i = 1; i <= n; i++) {
        while (N1 && Cst[ H3[1] ] < T[i]) {

            nod = H3[1];

            H2[++N2] = H3[1];
            up_heap2 (N2);

            H3[1] = H3[N3];
            N3--;
            Poz3[ H3[1] ] = 1;
            down_heap3 (1);

            H1[ Poz1[ nod ] ] = H1[N1];
            Poz1[ H1[ Poz1[ nod ] ] ] = Poz1[nod];

            N1--;
            down_heap1 ( Poz1[nod] );
            up_heap1 ( Poz1[nod] );
        }

        c1 = INF; c2 = INF;
        if (N1)
            c1 = Cst[H1[1]] + A[ H1[1] ];

        if (N2)
            c2 = T[i] + A[ H2[1] ];

        if (c1 <= c2) {
            Sol[i] = c1;
            nod = H1[1];
            Cst[ H1[1] ] = c1;
            down_heap1 (1);
            down_heap3 ( Poz3[nod] );
        }
        else {
            Sol[i] = c2;
            Cst[ H2[1] ] = c2;

            if ( Cst[ H2[1] ] > T[i + 1] && i < n ) {
                H1[ ++N1 ] = H2[1]; Poz1[ H1[N1] ] = N1;
                up_heap1 (N1);

                H3[ ++N3 ] = H2[1]; Poz3[ H3[N3] ] = N3;
                up_heap3 (N3);

                H2[1] = H2[N2];
                N2--;
                down_heap2 (1);
            }
            else {
               // down_heap2 (1);
            }
        }
    }
}

void citire () {

    int i;
    scanf ("%d %d %d", &n, &Na, &Nb);

    for (i = 1; i <= Na; i++)
        scanf ("%d", &A[i]);

    for (i = 1; i <= Nb; i++)
        scanf ("%d", &B[i]);
}

int main () {

    freopen ("fabrica.in", "r", stdin);
    freopen ("fabrica.out", "w", stdout);

    citire ();

    rezolva ();
    memcpy (T, Sol, sizeof (Sol));

    int i;
    int sol = 0;

    for (i = 1; i <= n; i++)
        if (sol < Sol[i]) sol = Sol[i];
    printf ("%d ", sol);

    Na = Nb;
    mempcpy (A, B, sizeof (B)); //

    rezolva ();

    sol = 0;
    for (i = 1; i <= n; i++)
        if (sol < Sol[i]) sol = Sol[i];
    printf ("%d\n", sol);

    return 0;
}