Untitled
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