Seat Reservation

[qiaobaaa]

ifndef _CRT_SECURE_NO_WARNINGS

define _CRT_SECURE_NO_WARNINGS

endif

include

include

include

include

using namespace std;

define MAXID 50003

define MAXN 2003

int N; struct theater { int id; int arr[101]; int avalcount; }tDB[MAXN + 1];

int mIDtotID[MAXID + 1]; int vis[101]; int tobemarked[101]; int curravalcount; struct Result { int id; int num; };

int dir[4] = { -1,1,-10,10 };

bool bfs(int start, int tID, int mID, int K) {

priority_queue<int, vector<int>, greater<int>>pq;
for (int i = 1; i <= 100; i++) {
    tobemarked[i] = 0;
}

int count = 0;
pq.push(start);
while (!pq.empty()) {
    int cur = pq.top();
    pq.pop();
    count++;

    tobemarked[cur] = 1;
    vis[cur] = 1;
    if (count == K)break;

    for (int j = 0; j < 4; j++) {
        if (cur % 10 == 0 && j == 1)
            continue;
        else if (cur % 10 == 1 && j == 0)
            continue;
        int newseatno = cur + dir[j];
        if (newseatno >= 1 && newseatno <= 100 && vis[newseatno] == 0 && tDB[tID].arr[newseatno] == 0 ) {
            pq.push(newseatno);
            vis[newseatno] = 1;
        }

    }

}

curravalcount -= count;
if (count == K) {
    for (int i = 1; i <= 100; i++) {
        if (tobemarked[i]) {
            tDB[tID].arr[i] = mID;
        }

    }
    return true;
}

return false;

}

void init(int N) { ::N = N; for (int i = 0; i <= MAXID; i++)mIDtotID[i] = 0; for (int i = 1; i <= N; i++) { tDB[i].id = i; tDB[i].avalcount = 100; for (int j = 1; j <= 100; j++) { tDB[i].arr[j] = 0; } }

}

Result reserveSeats(int mID, int K) { Result res; res.id = 0; res.num = 0;

for (int i = 1; i <= N; i++) {
    curravalcount = tDB[i].avalcount;
    if (curravalcount >= K) {

        for (int j = 1; j <= 100; j++)vis[j] = 0;
        for (int j = 1; j <= 100; j++) {
            if (tDB[i].arr[j] == 0 && vis[j] == 0 && curravalcount >= K) {
                if (bfs(j, i, mID, K)) {
                    res.id = i;
                    res.num = j;
                    mIDtotID[mID] = i;
                    tDB[i].avalcount -= K;
                    return res;
                }
            }
        }

    }
}

return res;

}

Result cancelReservation(int mID) {

Result res;
res.id = 0;
res.num = 0;
int tid = mIDtotID[mID];
res.id = tid;
int c = 0;
for (int i = 1; i <= 100; i++) {

    if (tDB[tid].arr[i] == mID) {
        res.num += i;
        tDB[tid].arr[i] = 0;
        c++;
    }
}
tDB[tid].avalcount += c;

return res;

}

[qiaobaaa]

vector queue algo ios