Cod sursa(job #586056)

Utilizator mihai995mihai995 mihai995 Data 30 aprilie 2011 13:31:34
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 2.31 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int N=300002;
struct proces{int finish,time,ind;} A[N],B[N];
int t[N],place[N],sizeA,sizeB,n,P;
vector<int> a[N],b[N];

ifstream in("fabrica.in");
ofstream out("fabrica.out");

inline bool cmp(proces a,proces b)
{
    return a.finish+a.time<b.finish+b.time;
}

inline void sch(proces v[],int a,int b)
{
    proces c=v[a];v[a]=v[b];v[b]=c;
    int d=place[a];place[a]=place[b];place[b]=d;
}

void up(proces v[],int n,int x)
{
    if (x>1 && cmp(v[x],v[x>>1]))
    {
        sch(v,x,x>>1);
        up(v,n,x>>1);
    }
}

void down(proces v[],int n,int x)
{
    int m=x,S=x<<1;
    if (S<=n && cmp(v[S],v[m]))
        m=S;
    S++;
    if (S<=n && cmp(v[S],v[m]))
        m=S;
    if (m!=x)
    {
        sch(v,m,x);
        down(v,n,m);
    }
}

void push(proces v[],int &n,proces x)
{
    v[++n]=x;
    place[x.ind]=n;
    up(v,n,n);
}

void pop(proces v[],int &n,int poz,proces &x)
{
    x=v[poz];
    v[poz]=v[n--];
    down(v,n,poz);
    up(v,n,poz);
    down(v,n,poz);
}

int bs(int v[],int x)
{
    int i,step=1<<16;
    for (i=0;step;step>>=1)
        if (i+step<=n && v[i+step]<x)
            i+=step;
    return i+1;
}

int procesare(vector<int> a[])
{
    int i,j,T;
    proces x;
    x.ind=0;
    for (i=1;i<=n;i++)
    {
        for (j=0;j<a[i].size();j++)
        {
            pop(B,sizeB,place[a[i][j]],x);
            x.finish=0;
            push(A,sizeA,x);
        }
        if (!sizeB || sizeA && cmp(A[1],B[1]))
        {
            pop(A,sizeA,1,x);
            T=t[i]+x.time;
            x.finish=T;
            push(B,sizeB,x);
        }
        else
        {
            B[1].finish+=B[1].time;
            T=B[1].finish;
            x.ind=B[1].ind;
            down(B,sizeB,1);
        }
        a[bs(t,T)].push_back(place[x.ind]);
        t[i]=T;
    }
    return t[n];
}

int main()
{
    int T1,T2,x,i,Q,W;
    in>>n>>Q>>W;
    sizeA=sizeB=0;
    for (i=1;i<=Q;i++)
    {
        in>>x;
        push(A,sizeA,(proces){0,x,i});
    }
    T1=procesare(a);
    sizeA=sizeB=0;
    for (i=1;i<=W;i++)
    {
        in>>x;
        push(A,sizeA,(proces){0,x,i});
    }
    T2=procesare(b);
    out<<T1<<" "<<T2<<"\n";
    return 0;
}