Untitled
unknown
plain_text
a year ago
5.6 kB
9
Indexable
Never
//package day23; import java.util.Comparator; import java.util.HashMap; import java.util.TreeSet; class UserSolution { class Memory{ int start,end,size; boolean isEmpty; Memory(int startt,int end, int size){ this.start = startt; this.end = end; this.size = size; } void updateValue(int startt,int end, int size){ this.start = startt; this.end = end; this.size = size; } } void addMemEmpty(Memory m){ emptyMem.add(m); emptyMemory.put(m.start, m); emptyMemory.put(m.end, m); } void removeMem(Memory m){ if (m != null) { emptyMem.remove(m); emptyMemory.remove(m.start); emptyMemory.remove(m.end); } } Comparator<Memory> com = new Comparator<Memory>() { public int compare(Memory m1 , Memory m2) { return m2.size == m1.size ? m1.start - m2.start : m1.size - m2.size; } }; int n; TreeSet<Memory> emptyMem = new TreeSet<>(com); HashMap<Integer, Memory> emptyMemory = new HashMap<Integer, Memory>(); HashMap<Integer, Memory> MemoryAllocated = new HashMap<Integer, Memory>(); public void init(int N) { n = N; emptyMem = new TreeSet<>(com); emptyMemory = new HashMap<Integer, Memory>(); MemoryAllocated = new HashMap<Integer, Memory>(); addMemEmpty(new Memory(0, n-1,n)); } public int allocate(int mSize) { Memory newAllocate = new Memory(0, 0, mSize); Memory empty = emptyMem.ceiling(newAllocate); // System.out.println("******" + empty.size); removeMem(empty); if (empty != null) { newAllocate = new Memory(empty.start, empty.start + mSize- 1, mSize); MemoryAllocated.put(newAllocate.start, newAllocate); // System.out.println("******" ); if (empty.size > mSize) { Memory newEmpty = new Memory(empty.start+mSize, empty.end, empty.size-mSize); addMemEmpty(newEmpty); } // System.out.println("******" + newAllocate.start); return newAllocate.start; } return -1; } public int release(int mAddr) { int res = -1; Memory m = MemoryAllocated.get(mAddr); if (m != null) { MemoryAllocated.remove(m.start); res = m.size; Memory m1 = emptyMemory.get(m.start-1); if (m1 != null) { removeMem(m1); m.updateValue(m1.start, m.end, m1.size+m.size); } Memory m2 = emptyMemory.get(m.end+1); if (m2 != null) { removeMem(m2); m.updateValue(m.start, m2.end, m2.size+m.size); } addMemEmpty(m); } // System.out.println("******" + res); return res; } } //////////////////////// #include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; vector<int> row[700]; vector<int> col[10000]; int mRow; int mCol; int vis[700][10000]; int cnt=0; queue<pair<int,int>> q; void init(int R, int C, int M, int mStructureR[30000], int mStructureC[30000]) { for (int i = 0; i < R; i++) { row[i] = { -1, C }; } for (int i = 0; i < C; i++) { col[i] = { -1, R }; } for (int i = 0; i < M; i++) { row[mStructureR[i]].push_back(mStructureC[i]); col[mStructureC[i]].push_back(mStructureR[i]); } for (int i = 0; i < R; i++) sort(row[i].begin(), row[i].end()); for (int i = 0; i < C; i++) sort(col[i].begin(), col[i].end()); mRow = R; mCol = C; } int minDamage(int mStartR, int mStartC, int mEndR, int mEndC) { int damage = 0; cnt++; if(mStartR==mEndR && mStartC==mEndC) return damage; q = {}; q.push({mStartR,mStartC}); vis[mStartR][mStartC] = cnt; while(!q.empty()) { int sz = q.size(); for(int i=0;i<sz;i++) { auto temp = q.front(); int x = temp.first; int y = temp.second; auto nextCol = lower_bound(row[x].begin(),row[x].end(),y); auto prevCol = nextCol - 1; if(x == mEndR && *prevCol < mEndC && *nextCol > mEndC) return damage; auto nextRow = lower_bound(col[y].begin(),col[y].end(),x); auto prevRow = nextRow - 1; if(y == mEndC && *prevRow < mEndR && *nextRow > mEndR) return damage; if (*nextCol != mCol && vis[x][*nextCol - 1] != cnt) { // down q.push({ x, *nextCol - 1 }); vis[x][*nextCol - 1] = cnt; } if (*prevCol != -1 && vis[x][*prevCol + 1] != cnt) { // up q.push({ x, *prevCol + 1 }); vis[x][*prevCol + 1] = cnt; } if (*prevRow != -1 && vis[*prevRow + 1][y] != cnt) { // left q.push({ *prevRow + 1, y }); vis[*prevRow + 1][y] = cnt; } if (*nextRow != mRow && vis[*nextRow - 1][y] != cnt) { //right q.push({ *nextRow - 1, y }); vis[*nextRow - 1][y] = cnt; } q.pop(); } damage++; } return -1; }