Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.7 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});
    }
    
    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 = m - availableRows.lower_bound({0, row})->first;

    // Cập nhật lại số chỗ trống cho hàng sau khi xóa từ
    availableRows.erase({m - mLen, row});
    availableRows.insert({m - startCol, row});
    
    id[mId] = 0;
    return row;
}
Leave a Comment