Untitled

#define MAXN    (100)
#define MAXL    (8)
 
 
#define MAXC    (10000)
#define MAXH    (1 << 15)
 
 
#define null    (0)
 
 
void mstrcpy(char dst[], const char src[])
{
    int c = 0;
    while ((dst[c] = src[c]) != 0) ++c;
}
 
 
int mstrcmp(const char str1[], const char str2[])
{
    int c = 0;
    while (str1[c] != 0 && str1[c] == str2[c]) ++c;
    return str1[c] - str2[c];
}
 
 
int durableTime;
 
 
struct Customer
{
    char mName[MAXL];
     
    int mBicycle;
    int mRentStartTime;
    int mTicketExpiredTime;
     
    void init(char uName[])
    {
        mstrcpy(mName, uName);
        mBicycle = -1;
        mTicketExpiredTime = -1;
    }        
};
 
 
int customerCnt;
Customer cus[MAXC];
 
 
Customer* getCustomer()
{
    return &cus[customerCnt++];
}
 
 
struct CustomerDB
{
    Customer* db[MAXH];
     
    int geth(char *s)
    {
        int ret = 0;
        while (*s != '\0')
            ret = (ret * 33 + *s++) % MAXH;
         
        return ret;
    }
     
    void init()
    {
        for (int i = 0; i < MAXH; ++i)
            db[i] = null;
    }
     
    Customer* find(char uName[])
    {
        int h = geth(uName);
         
        while (db[h] != null && mstrcmp(db[h]->mName, uName) != 0)
            h = (h + 1) % MAXH;
         
        if (db[h] == null)
        {
            db[h] = getCustomer();
            db[h]->init(uName);
        }
         
        return db[h];
    }
};
 
 
CustomerDB customerdb;
 
 
#define MAX_BICYCLE         (20001)
 
 
struct Que
{
    int arr[MAX_BICYCLE];
    int p1, p2;
     
    void init()
    {
        p1 = p2 = 0;
    }
     
    void push(int v)
    {
        arr[p2] = v;
        p2 = (p2 + 1) % MAX_BICYCLE;
    }
     
    void pop()
    {
        p1 = (p1 + 1) % MAX_BICYCLE;
    }
     
    int front()
    {
        return arr[p1];
    }
     
    bool empty()
    {
        return p1 == p2;
    }
};
 
 
struct Heap
{
    int arr[MAX_BICYCLE];
    int size;
     
    void init()
    {
        size = 0;
    }
 
 
    void push(int v)
    {
        if (size == MAX_BICYCLE)
            return;
 
 
        arr[size] = v;
 
 
        int cur = size++;
        while (cur > 0 && arr[cur] < arr[(cur - 1) / 2])
        {
            int t = arr[(cur - 1) / 2]; arr[(cur - 1) / 2] = arr[cur]; arr[cur] = t;
            cur = (cur - 1) / 2;
        }
    }
 
 
    void pop()
    {
        if (size <= 0) return;
 
 
        arr[0] = arr[--size];
 
 
        int cur = 0;
        while (cur * 2 + 1 < size)
        {
            int child = (cur + cur + 2 == size) || (arr[cur + cur + 1] < arr[cur + cur + 2]) ? cur + cur + 1 : cur + cur + 2;
 
 
            if (arr[cur] < arr[child])
                break;
 
 
            int t = arr[child]; arr[child] = arr[cur]; arr[cur] = t;
            cur = child;
        }
    }
     
    int top()
    {
        return arr[0];
    }
     
    bool empty()
    {
        return size == 0;
    }
};
 
 
int current;
 
 
struct RentalStation
{    
    int mDeliveryTime;
 
 
    Que orders;
    Heap bicycles;
     
    void init(int deliveryTime)
    {
        mDeliveryTime = deliveryTime;
         
        orders.init();
        bicycles.init();
    }
     
    void update(int current)
    {
        while (!orders.empty() && orders.front() <= current)
        {
            bicycles.push(0);
            orders.pop();
        }
    }
};
 
 
RentalStation stations[MAXN];
 
 
void init(int N, int durableTime, int deliveryTimes[MAXN])
{
    ::durableTime = durableTime;
 
 
    for (int i = 0; i < N; ++i)
        stations[i].init(deliveryTimes[i]);
     
    customerCnt = 0;
 
 
    customerdb.init();
     
    current = 0;
}
 
 
void addBicycle(int cTimestamp, int pID, int bicycleNum)
{
    current = cTimestamp;
 
 
    for (int i = 0; i < bicycleNum; ++i)
        stations[pID].bicycles.push(0);    
}
 
 
void buyTicket(int cTimestamp, char uName[MAXL], int validTime)
{
    current = cTimestamp;
     
    Customer* c = customerdb.find(uName);
 
 
    if (c->mTicketExpiredTime <= current)
        c->mTicketExpiredTime = current + validTime;
    else
        c->mTicketExpiredTime += validTime;
}
 
 
int rentBicycle(int cTimestamp, char uName[MAXL], int pID)
{
    current = cTimestamp;
     
    stations[pID].update(current);
 
 
    if (stations[pID].bicycles.empty())
        return -1;
 
 
    Customer* c = customerdb.find(uName);
     
    if (c->mBicycle != -1 || c->mTicketExpiredTime <= current)
        return -1;
     
    c->mBicycle = stations[pID].bicycles.top();
    stations[pID].bicycles.pop();
     
    c->mRentStartTime = current;
 
 
    return c->mBicycle;
}
 
 
int returnBicycle(int cTimestamp, char uName[MAXL], int pID)
{
    current = cTimestamp;
     
    Customer* c = customerdb.find(uName);
     
    if (c->mBicycle == -1)
        return -1;
 
 
    int bicycle = current - c->mRentStartTime + c->mBicycle;
     
    if (bicycle <= durableTime)
        stations[pID].bicycles.push(bicycle);
    else
        stations[pID].orders.push(current + stations[pID].mDeliveryTime);    
     
    c->mBicycle = -1;
     
    if (c->mTicketExpiredTime > current)
        return 0;
 
 
    return current - c->mTicketExpiredTime + 1;
}