Untitled

mail@pastecode.io avatar
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;
}