Untitled

mail@pastecode.io avatar
unknown
plain_text
23 days ago
1.9 kB
2
Indexable
Never
#include <iostream>
#include <set>
using namespace std;

const int MAX_ID = 50001;

int n, m, id[MAX_ID];
int rowStore[MAX_ID], colStore[MAX_ID];

set<pair<int, int>> availableRows; // {remaining slots, row index}

void init(int N, int M) {
    n = N;
    m = M;

    availableRows.clear();
    for (int i = 0; i < n; i++) {
        availableRows.insert({M, i}); // Tất cả các hàng đều có M chỗ trống
    }

    fill(id, id + MAX_ID, 0);
    fill(rowStore, rowStore + MAX_ID, -1);
    fill(colStore, colStore + MAX_ID, -1);
}

int writeWord(int mId, int mLen) {
    auto it = availableRows.lower_bound({mLen, 0});

    if (it == availableRows.end()) {
        return -1; // Không có hàng nào đủ chỗ trống
    }

    int curRow = it->second;
    int remainingSlots = it->first;

    // Xóa hàng này khỏi tập hợp để cập nhật lại số chỗ trống
    availableRows.erase(it);

    colStore[mId] = m - remainingSlots; // Vị trí bắt đầu của từ
    rowStore[mId] = curRow;

    // Cập nhật lại số chỗ trống và đưa lại vào tập hợp nếu vẫn còn chỗ
    remainingSlots -= mLen;
    if (remainingSlots > 0) {
        availableRows.insert({remainingSlots, curRow});
    }

    id[mId] = 1;
    return curRow;
}

int eraseWord(int mId) {
    if (id[mId] == 0) {
        return -1;
    }

    int row = rowStore[mId];
    int startCol = colStore[mId];
    int mLen = 0;

    // Xác định độ dài của từ để cập nhật số chỗ trống
    while (startCol + mLen < m && id[mId] == 1 && colStore[mId] == startCol) {
        mLen++;
    }

    // Cập nhật lại số chỗ trống trong hàng
    auto it = availableRows.find({m - startCol, row});
    if (it != availableRows.end()) {
        availableRows.erase(it);
    }
    availableRows.insert({m - startCol + mLen, row});

    id[mId] = 0;
    return row;
}
Leave a Comment