707k score for https://codeforces.com/contest/1724/problem/A

Solution.cs

using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;
using System.Linq;
using System;


public abstract class Heap<T> : IEnumerable<T>
{
    private const int InitialCapacity = 0;
    private const int GrowFactor = 2;
    private const int MinGrow = 1;

    private int _capacity = InitialCapacity;
    private T[] _heap = new T[InitialCapacity];
    private int _tail = 0;

    public int Count { get { return _tail; } }
    public int Capacity { get { return _capacity; } }

    protected Comparer<T> Comparer { get; private set; }
    protected abstract bool Dominates(T x, T y);

    protected Heap() : this(Comparer<T>.Default)
    {
    }

    protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
    {
    }

    protected Heap(IEnumerable<T> collection)
        : this(collection, Comparer<T>.Default)
    {
    }

    protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
    {
        if (collection == null) throw new ArgumentNullException("collection");
        if (comparer == null) throw new ArgumentNullException("comparer");

        Comparer = comparer;

        foreach (var item in collection)
        {
            if (Count == Capacity)
                Grow();

            _heap[_tail++] = item;
        }

        for (int i = Parent(_tail - 1); i >= 0; i--)
            BubbleDown(i);
    }

    public void Add(T item)
    {
        if (Count == Capacity)
            Grow();

        _heap[_tail++] = item;
        BubbleUp(_tail - 1);
    }

    private void BubbleUp(int i)
    {
        if (i == 0 || Dominates(_heap[Parent(i)], _heap[i]))
            return; //correct domination (or root)

        Swap(i, Parent(i));
        BubbleUp(Parent(i));
    }

    public T GetMin()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        return _heap[0];
    }

    public T ExtractDominating()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        T ret = _heap[0];
        _tail--;
        Swap(_tail, 0);
        BubbleDown(0);
        return ret;
    }

    private void BubbleDown(int i)
    {
        int dominatingNode = Dominating(i);
        if (dominatingNode == i) return;
        Swap(i, dominatingNode);
        BubbleDown(dominatingNode);
    }

    private int Dominating(int i)
    {
        int dominatingNode = i;
        dominatingNode = GetDominating(YoungChild(i), dominatingNode);
        dominatingNode = GetDominating(OldChild(i), dominatingNode);

        return dominatingNode;
    }

    private int GetDominating(int newNode, int dominatingNode)
    {
        if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
            return newNode;
        else
            return dominatingNode;
    }

    private void Swap(int i, int j)
    {
        T tmp = _heap[i];
        _heap[i] = _heap[j];
        _heap[j] = tmp;
    }

    private static int Parent(int i)
    {
        return (i + 1) / 2 - 1;
    }

    private static int YoungChild(int i)
    {
        return (i + 1) * 2 - 1;
    }

    private static int OldChild(int i)
    {
        return YoungChild(i) + 1;
    }

    private void Grow()
    {
        int newCapacity = _capacity * GrowFactor + MinGrow;
        var newHeap = new T[newCapacity];
        Array.Copy(_heap, newHeap, _capacity);
        _heap = newHeap;
        _capacity = newCapacity;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _heap.Take(Count).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class MaxHeap<T> : Heap<T>
{
    public MaxHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MaxHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) >= 0;
    }
}

public class MinHeap<T> : Heap<T>
{
    public MinHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MinHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MinHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) <= 0;
    }
}

public class VirtualMachineCreateInstruction
{
    private const double SOFT_BONUS = 3;
    private const double SAME_RACK_BONUS = 1.5;
    public int Amount;
    public int NeededCPU;
    public VirtualMachine VirtualMachine;
    public PlacementGroup PlacementGroup;
    public int PartitionIndex;
    public int[] Indices;

    public VirtualMachineCreateInstruction(int amount, VirtualMachine virtualMachine, PlacementGroup placementGroup, int partitionIndex, int[] vmIndices)
    {
        this.Amount = amount;
        this.VirtualMachine = virtualMachine;
        this.PlacementGroup = placementGroup;
        this.PartitionIndex = partitionIndex;
        this.Indices = vmIndices;
        PlacementGroup.Requests.Add(this);

        this.NeededCPU = amount * virtualMachine.CPU * virtualMachine.NumaCount;
    }

    public bool Create()
    {
        // if (Indices[0] > 6973) Debugger.Break();
#if DEBUG
        Dictionary<string, int> freq = new Dictionary<string, int>();
        Dictionary<string, double> scores = new Dictionary<string, double>();
        foreach (PhysicalMachine m in Solution.PhysicalMachines)
        {
            string s = m.ToString().Split('@')[0].Trim();
            if (!freq.ContainsKey(s))
            {
                freq[s] = 0;
                m.UpdatePenalty(VirtualMachine);
                scores[s] = m.Penalty;
            }
            freq[s]++;
        }
        Console.Error.WriteLine("group: " + PlacementGroup + "    partition: " + PartitionIndex + "   amount: " + Amount + "   nodes: " + VirtualMachine.NumaCount + "   CPU: " + VirtualMachine.CPU + "   RAM: " + VirtualMachine.RAM);
#endif

        List<PhysicalMachine> candidates = Solution.PhysicalMachines
            .Where(m => m.CanPlaceInstance(VirtualMachine) > 0)
            .ToList();

        if (candidates.Count == 0)
        {
            Console.WriteLine(-1);
            return false;
        }
        // if (PlacementGroup.ID == 22 && PartitionIndex == 5) Debugger.Break();

        List<PhysicalMachine> toTake = new List<PhysicalMachine>();
        if (PlacementGroup.RackAffinity != ConstraintType.None || PlacementGroup.NetworkAffinity != ConstraintType.None || PlacementGroup.NumberPartitions != 0)
        {
            foreach (Rack rack in Solution.Racks) rack.VMCapacity = rack.PhysicalMachines.Sum(p => p.CanPlaceInstance(VirtualMachine));
            foreach (NetworkDomain network in Solution.Domains) network.VMCapacity = network.Racks.Sum(r => r.VMCapacity);
        }
        if (PlacementGroup.RackAffinity == ConstraintType.Hard)
        {
            // place on same rack
            if (PlacementGroup.Rack == null)
            {
                var byRack = candidates.GroupBy(c => c.Rack);
                toTake = byRack.OrderByDescending(g => g.Key.VMCapacity).First().ToList();
                PlacementGroup.Rack = toTake[0].Rack;
            }
            else toTake = candidates.Where(c => c.Rack == PlacementGroup.Rack).ToList();
        }
        else if (PlacementGroup.NetworkAffinity == ConstraintType.Hard)
        {
            // place in same network
            if (PlacementGroup.NetworkDomain == null)
            {
                var byNetwork = candidates.GroupBy(c => c.Rack.NetworkDomain);
                toTake = byNetwork.OrderByDescending(g => g.Key.VMCapacity).First().ToList();
                PlacementGroup.NetworkDomain = toTake[0].Rack.NetworkDomain;
                PlacementGroup.NetworkDomain.PlacementGroups.Add(PlacementGroup);
            }
            else toTake = candidates.Where(c => c.Rack.NetworkDomain == PlacementGroup.NetworkDomain).ToList();
        }
        else toTake = candidates;

        List<PhysicalMachine> priority = toTake.ToList();
        if (PlacementGroup.RackAffinity == ConstraintType.Soft)
        {
            // place on same rack
            if (PlacementGroup.Rack == null)
            {
                var byRack = toTake.GroupBy(c => c.Rack);
                priority = byRack.Count() == 1 ? byRack.First().ToList() : byRack.OrderByDescending(g => g.Key.VMCapacity).ElementAt(1).ToList();
                if (priority[0].Rack.VMCapacity < Amount)
                {
                    PlacementGroup.Rack = new Rack();
                    priority.Clear();
                }
                else PlacementGroup.Rack = priority[0].Rack;
            }
            else
            {
                if (PlacementGroup.Rack.VMCapacity < Amount)
                {
                    PlacementGroup.Rack = new Rack();
                    priority.Clear();
                }
                else priority = candidates.Where(c => c.Rack == PlacementGroup.Rack).ToList();
            }
        }
        else if (PlacementGroup.NetworkAffinity == ConstraintType.Soft)
        {
            // place in same network
            if (PlacementGroup.NetworkDomain == null)
            {
                var byNetwork = toTake.GroupBy(c => c.Rack.NetworkDomain);
                priority = byNetwork.Count() == 1 ? byNetwork.First().ToList() : byNetwork.OrderByDescending(g => g.Key.VMCapacity).ElementAt(1).ToList();
                if (priority[0].Rack.NetworkDomain.VMCapacity < Amount)
                {
                    PlacementGroup.NetworkDomain = new NetworkDomain();
                    priority.Clear();
                }
                else PlacementGroup.NetworkDomain = priority[0].Rack.NetworkDomain;
            }
            else
            {
                if (PlacementGroup.NetworkDomain.VMCapacity < Amount)
                {
                    PlacementGroup.NetworkDomain = new NetworkDomain();
                    priority.Clear();
                }
                else priority = candidates.Where(c => c.Rack.NetworkDomain == PlacementGroup.NetworkDomain).ToList();
            }
        }
        if (PlacementGroup.MaxVMsPerPM > 0)
        {
            List<PhysicalMachine> full = new List<PhysicalMachine>();
            foreach (PhysicalMachine m in toTake)
            {
                if (PlacementGroup.VMsPerPM.ContainsKey(m) && PlacementGroup.VMsPerPM[m] >= PlacementGroup.MaxVMsPerPM) full.Add(m);
            }
            priority = priority.Except(full).ToList();
        }

        foreach (PhysicalMachine m in toTake) m.UpdatePenalty(VirtualMachine);
        foreach (PhysicalMachine m in priority) m.Penalty -= SOFT_BONUS;

#if DEBUG
        var tmp = toTake.OrderBy(m => m.Penalty).ToList();
        //if (Indices[0] > 6973) Debugger.Break();
#endif

        List<string> solution = new List<string>();
        if (PartitionIndex == -1) // one per partition
        {
            toTake = toTake.OrderBy(p => p.Penalty).ToList();
            for (int i = 0; i < Amount; i++)
            {
                List<PhysicalMachine> inPartition = PlacementGroup.InPartition(i + 1, toTake);
                foreach (PhysicalMachine m in inPartition) m.Penalty -= 1.5;
                inPartition.AddRange(PlacementGroup.WithoutPartition(toTake));
                if (inPartition.Count == 0) break;
                PhysicalMachine machine = inPartition[0];
                for (int j = 1; j < inPartition.Count; j++)
                {
                    if (inPartition[j].Penalty < machine.Penalty) machine = inPartition[j];
                }

                VirtualMachine vm = new VirtualMachine { PlacementGroup = PlacementGroup, CPU = this.VirtualMachine.CPU, RAM = this.VirtualMachine.RAM, NumaCount = this.VirtualMachine.NumaCount };
                vm.Nodes = machine.PlaceInstance(PlacementGroup, VirtualMachine, i + 1);
                Solution.VirtualMachines[Indices[i]] = vm;
                solution.Add($"{machine.Rack.NetworkDomain.ID} {machine.Rack.ID} {machine.ID} {string.Join(" ", vm.Nodes.Select(n => n.ID))}");
                if (PlacementGroup.RackAffinity == ConstraintType.Soft && PlacementGroup.Rack != machine.Rack)
                {
                    priority.Clear();
                    PlacementGroup.Rack = new Rack();
                }
                else if (PlacementGroup.NetworkAffinity == ConstraintType.Soft && PlacementGroup.NetworkDomain != machine.Rack.NetworkDomain)
                {
                    priority.Clear();
                    PlacementGroup.NetworkDomain = new NetworkDomain();
                }
            }
        }
        else
        {
            MinHeap<PhysicalMachineHeapItem> generalHeap = new MinHeap<PhysicalMachineHeapItem>();
            if (PartitionIndex == 0)
            {
                foreach (PhysicalMachine m in toTake) generalHeap.Add(new PhysicalMachineHeapItem(m));
            }
            else
            {
                foreach (PhysicalMachine m in PlacementGroup.InPartition(PartitionIndex, toTake))
                {
                    m.Penalty -= SAME_RACK_BONUS;
                    generalHeap.Add(new PhysicalMachineHeapItem(m));
                }
                foreach (PhysicalMachine m in PlacementGroup.WithoutPartition(toTake)) generalHeap.Add(new PhysicalMachineHeapItem(m));
            }
            for (int i = 0; i < Amount; i++)
            {
                PhysicalMachine machine = null;
                while (generalHeap.Count > 0)
                {
                    machine = generalHeap.ExtractDominating().Machine;
                    if (machine.CanPlaceInstance(VirtualMachine) > 0) break;
                }
                if (machine == null || machine.CanPlaceInstance(VirtualMachine) == 0) break;
                bool newPartition = !PlacementGroup.Partitions.Keys.Any(m => m.Rack == machine.Rack);

                VirtualMachine vm = new VirtualMachine { PlacementGroup = PlacementGroup, CPU = this.VirtualMachine.CPU, RAM = this.VirtualMachine.RAM, NumaCount = this.VirtualMachine.NumaCount };
                //if (machine.GlobalID == 35) Debugger.Break();
                //machine.InstanceMatchFactor(VirtualMachine);
                vm.Nodes = machine.PlaceInstance(PlacementGroup, VirtualMachine, PartitionIndex);
                //if (machine.ToString() == "117:11 | 98:0") Debugger.Break();
                Solution.VirtualMachines[Indices[i]] = vm;
                solution.Add($"{machine.Rack.NetworkDomain.ID} {machine.Rack.ID} {machine.ID} {string.Join(" ", vm.Nodes.Select(n => n.ID))}");
                if (PlacementGroup.RackAffinity == ConstraintType.Soft && PlacementGroup.Rack != machine.Rack)
                {
                    priority.Clear();
                    PlacementGroup.Rack = new Rack();
                }
                else if (PlacementGroup.NetworkAffinity == ConstraintType.Soft && PlacementGroup.NetworkDomain != machine.Rack.NetworkDomain)
                {
                    priority.Clear();
                    PlacementGroup.NetworkDomain = new NetworkDomain();
                }

                machine.UpdatePenalty(VirtualMachine);
                if (PlacementGroup.MaxVMsPerPM > 0 && PlacementGroup.VMsPerPM[machine] == PlacementGroup.MaxVMsPerPM) priority.Remove(machine);
                if (priority.Contains(machine)) machine.Penalty -= SOFT_BONUS;

                if (PartitionIndex == 0)
                {
                    if (machine.CanPlaceInstance(VirtualMachine) > 0) generalHeap.Add(new PhysicalMachineHeapItem(machine));
                }
                else
                {
                    if (newPartition)
                    {
                        foreach (PhysicalMachine m in machine.Rack.PhysicalMachines)
                        {
                            if (m.CanPlaceInstance(VirtualMachine) > 0)
                            {
                                m.Penalty -= SAME_RACK_BONUS;
                                generalHeap.Add(new PhysicalMachineHeapItem(m)); // double entry with lower penalty
                            }
                        }
                    }
                    else if (machine.CanPlaceInstance(VirtualMachine) > 0)
                    {
                        machine.Penalty -= SAME_RACK_BONUS;
                        generalHeap.Add(new PhysicalMachineHeapItem(machine));
                    }
                }
            }
        }

        if (solution.Count < Amount)
        {
            Console.Error.WriteLine("total CPU free: " + Solution.PhysicalMachines.SelectMany(p => p.Nodes).Sum(n => n.FreeCPU));
            Console.Error.WriteLine("total RAM free: " + Solution.PhysicalMachines.SelectMany(p => p.Nodes).Sum(n => n.FreeRAM));
            Console.WriteLine(-1);
            return false;
        }
        foreach (string s in solution) Console.WriteLine(s);
        return true;
    }
} 
public enum ConstraintType
{
    None,
    Soft,
    Hard
}

public enum InstructionType
{
    PlacementGroupCreate = 1,
    VirtualMachineCreate = 2,
    VirtualMachineDelete = 3,
    Terminate = 4
}

public class NumaNode
{
    public int ID;
    public int MaxCPU;
    public int MaxRAM;
    public int CurrentCPU;
    public int CurrentRAM;
    public int FreeCPU => MaxCPU - CurrentCPU;
    public int FreeRAM => MaxRAM - CurrentRAM;

    public static double[,] Score;
    public static double[,] ScoreSingle;
    public PhysicalMachine PhysicalMachine;

    public override string ToString()
    {
        return FreeCPU + ":" + FreeRAM;
    }
}


public class NetworkDomain
{
    public int ID;
    public List<Rack> Racks;
    public List<PlacementGroup> PlacementGroups = new List<PlacementGroup>();
    public int VMCapacity;

    public void AddRacks(int r)
    {
        Racks = Enumerable.Range(1, r).Select(i => new Rack { ID = i, NetworkDomain = this }).ToList();
    }
}


public class Rack
{
    public int ID;
    public NetworkDomain NetworkDomain;
    public List<PhysicalMachine> PhysicalMachines;
    public int VMCapacity;
    public bool PartitionGroup;

    public void AddPhysicalMachines(int s)
    {
        PhysicalMachines = Enumerable.Range(1, s).Select(i => new PhysicalMachine { ID = i, Rack = this }).ToList();
    }

    public override string ToString() => NetworkDomain.ID + "/" + this.ID;
}


public class VirtualMachine
{
    public int ID;
    public int NumaCount;
    public int CPU; // per node
    public int RAM; // per node
    public PlacementGroup PlacementGroup;

    public NumaNode[] Nodes;
    public void Allocate(NumaNode[] nodes)
    {
        this.Nodes = nodes;
        foreach (NumaNode node in Nodes)
        {
            node.CurrentCPU += CPU;
            node.CurrentRAM += RAM;
        }
    }

    public void Delete()
    {
        foreach (NumaNode node in Nodes)
        {
            node.CurrentCPU -= CPU;
            node.CurrentRAM -= RAM;
        }

        PhysicalMachine machine = Nodes[0].PhysicalMachine;
        if (PlacementGroup.InUse[machine] == 1 && PlacementGroup.Partitions.ContainsKey(machine)) PlacementGroup.Partitions.Remove(machine);
        if (PlacementGroup.InUse[machine] == 1) PlacementGroup.InUse.Remove(machine);
        else PlacementGroup.InUse[machine]--;
        if (PlacementGroup.VMsPerPM[machine] == 1) PlacementGroup.VMsPerPM.Remove(machine);
        else PlacementGroup.VMsPerPM[machine]--;
    }

    public override string ToString()
    {
        if (Nodes == null && NumaCount == 1) return CPU + ":" + RAM;
        if (Nodes == null) return NumaCount + " x " + CPU + ":" + RAM;
        return string.Join(" | ", Nodes.ToList());
    }
}


public class PlacementGroup
{
    public int ID;
    public ConstraintType NetworkAffinity;
    public ConstraintType RackAffinity;
    public int NumberPartitions; // hard rack anti-affinity
    public int MaxVMsPerPM; // soft PM anti-affinity
    public Dictionary<PhysicalMachine, int> InUse = new Dictionary<PhysicalMachine, int>();
    public Dictionary<PhysicalMachine, int> Partitions = new Dictionary<PhysicalMachine, int>();
    public Dictionary<PhysicalMachine, int> VMsPerPM = new Dictionary<PhysicalMachine, int>();
    public Rack Rack;
    public NetworkDomain NetworkDomain;
    public List<VirtualMachineCreateInstruction> Requests = new List<VirtualMachineCreateInstruction>();

    public int NeededCPU()
    {
        return Requests.Sum(r => r.NeededCPU);
    }

    public PlacementGroup(int id, int kj, int aj, int nj, int rj)
    {
        this.ID = id;
        this.NumberPartitions = kj;
        this.MaxVMsPerPM = aj;
        this.NetworkAffinity = (ConstraintType)nj;
        this.RackAffinity = (ConstraintType)rj;
    }

    public override string ToString()
    {
        return $"{ID} {NetworkAffinity} {RackAffinity} {NumberPartitions} {MaxVMsPerPM}";
    }

    public List<PhysicalMachine> InPartition(int partitionIndex, List<PhysicalMachine> toTake)
    {
        List<Rack> partitionRack = Partitions.Where(p => p.Value == partitionIndex).Select(p => p.Key.Rack).Distinct().ToList();
        return toTake.Where(t => partitionRack.Contains(t.Rack)).ToList();
    }

    public List<PhysicalMachine> WithoutPartition(List<PhysicalMachine> toTake)
    {
        List<Rack> partitionRack = Partitions.Select(p => p.Key.Rack).Distinct().ToList();
        return toTake.Where(t => !partitionRack.Contains(t.Rack)).ToList();
    }

    public PhysicalMachine GetFromPartition(List<PhysicalMachine> toTake, int partitionIndex)
    {
        List<Rack> partitionRack = Partitions.Where(p => p.Value == partitionIndex).Select(p => p.Key.Rack).Distinct().ToList();
        List<Rack> otherRack = Partitions.Where(p => p.Value != partitionIndex).Select(p => p.Key.Rack).Distinct().ToList();
        List<PhysicalMachine> inPartition = toTake.Where(t => partitionRack.Contains(t.Rack)).ToList();
        if (inPartition.Count > 0)
        {
            Partitions[inPartition[^1]] = partitionIndex;
            return inPartition[^1];
        }
        List<PhysicalMachine> noPartition = toTake.Where(t => !otherRack.Contains(t.Rack)).ToList();
        if (noPartition.Count > 0)
        {
            Partitions[noPartition[^1]] = partitionIndex;
            return noPartition[^1];
        }
        return null;
    }
}


public class PhysicalMachine
{
    public int ID;
    public int GlobalID;
    public Rack Rack;
    public List<NumaNode> Nodes = new List<NumaNode>();
    public double Penalty;
    private double random;

    private static int idCounter;
    public PhysicalMachine()
    {
        random = Solution.Random.NextDouble();
        GlobalID = idCounter++;
    }

    public int CanPlaceInstance(VirtualMachine requirement)
    {
        if (requirement.NumaCount == 1)
        {
            int result = 0;
            foreach (NumaNode node in Nodes)
            {
                if (node.FreeCPU >= requirement.CPU && node.FreeRAM >= requirement.RAM)
                {
                    result += Math.Min(node.FreeCPU / requirement.CPU, node.FreeRAM / requirement.RAM); // TODO lookup?
                }
            }
            return result; 
        }

        int arrayIndex = 0;
        foreach (NumaNode node in Nodes)
        {
            if (node.FreeCPU >= requirement.CPU && node.FreeRAM >= requirement.RAM)
            {
                currentMachines[arrayIndex++] = Math.Min(node.FreeCPU / requirement.CPU, node.FreeRAM / requirement.RAM);
            }
        }
        if (arrayIndex < requirement.NumaCount) return 0;
        for (int i = 0; i < arrayIndex; i++)
        {
            for (int j = i + 1; j < arrayIndex; j++)
            {
                if (currentMachines[i] > currentMachines[j])
                {
                    int tmp = currentMachines[j];
                    currentMachines[j] = currentMachines[i];
                    currentMachines[i] = tmp;
                }
            }
        }
        if (arrayIndex == 2) return currentMachines[0];
        if (arrayIndex == 3) return Math.Min(currentMachines[0] + currentMachines[1], currentMachines[2]);
        int sum = currentMachines[0] + currentMachines[1] + currentMachines[2] + currentMachines[3];
        return Math.Min(sum / 2, sum - currentMachines[3]);
    }

    public NumaNode[] PlaceInstance(PlacementGroup placementGroup, VirtualMachine virtualMachine, int partition = 0)
    {
        //if (this.ToString()=="44:88 | 48:96") System.Diagnostics.Debugger.Break();
        if (placementGroup.NumberPartitions > 0) Rack.PartitionGroup = true;
        if (!placementGroup.InUse.ContainsKey(this)) placementGroup.InUse[this] = 1;
        else placementGroup.InUse[this]++;
        if (partition != 0) placementGroup.Partitions[this] = partition;
        if (placementGroup.VMsPerPM.ContainsKey(this)) placementGroup.VMsPerPM[this]++;
        else placementGroup.VMsPerPM[this] = 1;
        NumaNode[] result = new NumaNode[virtualMachine.NumaCount];

        double bestRemaining = -100;
        if (virtualMachine.NumaCount == 1)
        {
            foreach (NumaNode toSubtract in this.Nodes)
            {
                if (toSubtract.FreeCPU < virtualMachine.CPU || toSubtract.FreeRAM < virtualMachine.RAM) continue;
                toSubtract.CurrentCPU += virtualMachine.CPU;
                toSubtract.CurrentRAM += virtualMachine.RAM;
                double subtractScore = ComputeScore();
                toSubtract.CurrentCPU -= virtualMachine.CPU;
                toSubtract.CurrentRAM -= virtualMachine.RAM;
                if (subtractScore > bestRemaining)
                {
                    bestRemaining = subtractScore;
                    result[0] = toSubtract;
                }
            }
        }
        else
        {
            for (int i = 0; i < this.Nodes.Count; i++)
            {
                if (Nodes[i].FreeCPU < virtualMachine.CPU || Nodes[i].FreeRAM < virtualMachine.RAM) continue;
                Nodes[i].CurrentCPU += virtualMachine.CPU;
                Nodes[i].CurrentRAM += virtualMachine.RAM;
                for (int j = i + 1; j < this.Nodes.Count; j++)
                {
                    if (Nodes[j].FreeCPU < virtualMachine.CPU || Nodes[j].FreeRAM < virtualMachine.RAM) continue;
                    Nodes[j].CurrentCPU += virtualMachine.CPU;
                    Nodes[j].CurrentRAM += virtualMachine.RAM;
                    double subtractScore = ComputeScore();
                    Nodes[j].CurrentCPU -= virtualMachine.CPU;
                    Nodes[j].CurrentRAM -= virtualMachine.RAM;
                    if (subtractScore > bestRemaining)
                    {
                        bestRemaining = subtractScore;
                        result[0] = Nodes[i];
                        result[1] = Nodes[j];
                    }
                }
                Nodes[i].CurrentCPU -= virtualMachine.CPU;
                Nodes[i].CurrentRAM -= virtualMachine.RAM;
            }
        }

        foreach (NumaNode node in result)
        {
            node.CurrentCPU += virtualMachine.CPU;
            node.CurrentRAM += virtualMachine.RAM;
        }

        return result;
    }

    public void UpdatePenalty(VirtualMachine virtualMachine)
    {
        Penalty = 100;

        if (Solution.FastMode)
        {
            bool equal = true;
            foreach (NumaNode node in Nodes)
            {
                equal &= node.FreeCPU == Nodes[0].FreeCPU && node.FreeRAM == Nodes[0].FreeRAM;
                if (node.FreeCPU < virtualMachine.CPU || node.FreeRAM < virtualMachine.RAM) continue;
                double currentLoss = NumaNode.Score[node.FreeCPU, node.FreeRAM] - NumaNode.Score[node.FreeCPU - virtualMachine.CPU, node.FreeRAM - virtualMachine.RAM];
                Penalty = Math.Min(Penalty, currentLoss);
                if (!equal) Penalty -= 1e-6;
            }
        }
        else
        {
            double initialScore = ComputeScore();
            if (virtualMachine.NumaCount == 1)
            {
                foreach (NumaNode toSubtract in this.Nodes)
                {
                    if (toSubtract != this.Nodes[0] && toSubtract.FreeCPU == Nodes[0].FreeCPU && toSubtract.FreeRAM == Nodes[0].FreeRAM) continue;
                    if (toSubtract.FreeCPU < virtualMachine.CPU || toSubtract.FreeRAM < virtualMachine.RAM) continue;
                    toSubtract.CurrentCPU += virtualMachine.CPU;
                    toSubtract.CurrentRAM += virtualMachine.RAM;
                    double subtractScore = ComputeScore();
                    toSubtract.CurrentCPU -= virtualMachine.CPU;
                    toSubtract.CurrentRAM -= virtualMachine.RAM;
                    if (initialScore - subtractScore < Penalty) Penalty = initialScore - subtractScore;
                }
            }
            else
            {
                for (int i = 0; i < this.Nodes.Count; i++)
                {
                    if (Nodes[i].FreeCPU < virtualMachine.CPU || Nodes[i].FreeRAM < virtualMachine.RAM) continue;
                    if (i > 0 && Nodes[i].FreeCPU == Nodes[0].FreeCPU && Nodes[i].FreeRAM == Nodes[0].FreeRAM) continue;
                    Nodes[i].CurrentCPU += virtualMachine.CPU;
                    Nodes[i].CurrentRAM += virtualMachine.RAM;
                    for (int j = i + 1; j < this.Nodes.Count; j++)
                    {
                        if (Nodes[j].FreeCPU < virtualMachine.CPU || Nodes[j].FreeRAM < virtualMachine.RAM) continue;
                        Nodes[j].CurrentCPU += virtualMachine.CPU;
                        Nodes[j].CurrentRAM += virtualMachine.RAM;
                        double subtractScore = ComputeScore();
                        Nodes[j].CurrentCPU -= virtualMachine.CPU;
                        Nodes[j].CurrentRAM -= virtualMachine.RAM;
                        if (initialScore - subtractScore < Penalty) Penalty = initialScore - subtractScore;
                    }
                    Nodes[i].CurrentCPU -= virtualMachine.CPU;
                    Nodes[i].CurrentRAM -= virtualMachine.RAM;
                }
            }
        }

        Penalty += 1e-6 * random;
        if (Rack.ID % 2 == 0) Penalty += 1e-6;
        if (Rack.NetworkDomain.ID % 2 == 0) Penalty += 1e-6;
    }

    private static int[] currentMachines = new int[4];
    private static int[] maxMachines = new int[4];
    private double ComputeScore()
    {
        double result = 0;
        foreach (NumaNode node in Nodes) result += NumaNode.ScoreSingle[node.FreeCPU, node.FreeRAM];
        foreach (VirtualMachine machine in Solution.VirtualMachinesDoubles) // TODO can be reduced more to exclude perfect divisors of current VM
        {
            int arrayIndex = 0;
            foreach (NumaNode node in Nodes)
            {
                maxMachines[arrayIndex] = Math.Min(node.MaxCPU / machine.CPU, node.MaxRAM / machine.RAM);
                currentMachines[arrayIndex++] = Math.Min(Math.Max(1, node.FreeCPU) / machine.CPU, Math.Max(1, node.FreeRAM) / machine.RAM);
            }
            for (int i = 0; i < arrayIndex; i++)
            {
                for (int j = i + 1; j < arrayIndex; j++)
                {
                    if (currentMachines[i] > currentMachines[j])
                    {
                        int tmp = currentMachines[j];
                        currentMachines[j] = currentMachines[i];
                        currentMachines[i] = tmp;
                    }
                    if (maxMachines[i] > maxMachines[j])
                    {
                        int tmp = maxMachines[j];
                        maxMachines[j] = maxMachines[i];
                        maxMachines[i] = tmp;
                    }
                }
            }
            double maxSum = 0;
            int currentSum = currentMachines[0];
            for (int i = 0; i < arrayIndex; i += 2) maxSum += maxMachines[i];
            if (arrayIndex == 4)
            {
                currentSum += currentMachines[1] + currentMachines[2] + currentMachines[3];
                currentSum = Math.Min(currentSum / 2, currentSum - currentMachines[3]);
            }
            result += currentSum / maxSum;
        }
        return result;
    }
 
    public override string ToString()
    {
        return string.Join(" | ", Nodes) + " @" + Rack + "/" + this.ID;
    }
}

public class PhysicalMachineHeapItem : IComparable<PhysicalMachineHeapItem>
{
    public PhysicalMachine Machine;
    public double Penalty;

    public PhysicalMachineHeapItem(PhysicalMachine machine)
    {
        this.Machine = machine;
        this.Penalty = machine.Penalty;
    }

    public int CompareTo(PhysicalMachineHeapItem other) => this.Penalty.CompareTo(other.Penalty);
}


public class Solution
{
    public static List<NetworkDomain> Domains;
    public static List<Rack> Racks;
    public static List<PhysicalMachine> PhysicalMachines;
    public static Dictionary<int, PlacementGroup> PlacementGroups = new Dictionary<int, PlacementGroup>();
    public static List<VirtualMachine> VirtualMachinesTypes = new List<VirtualMachine>();
    public static List<VirtualMachine> VirtualMachinesDoubles = new List<VirtualMachine>();
    public static Dictionary<int, VirtualMachine> VirtualMachines = new Dictionary<int, VirtualMachine>();
#if DEBUG
    public static Random Random = new Random(0);
#else
    public static Random Random = new Random();
#endif
    public static bool FastMode = false;

    private static int[] ReadInts()
    {
        int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
#if DEBUG
        Console.Error.WriteLine(string.Join(" ", nums));
#endif
        return nums;
    }

    private static int ReadInt() => ReadInts()[0];

    public static void Main(string[] args)
    {
        int[] nums = ReadInts();
        int n = nums[0], r = nums[1], s = nums[2], k = nums[3];
        Domains = Enumerable.Range(1, n).Select(i => new NetworkDomain { ID = i }).ToList();
        foreach (NetworkDomain domain in Domains) domain.AddRacks(r);
        Racks = Domains.SelectMany(d => d.Racks).ToList();
        foreach (Rack rack in Racks) rack.AddPhysicalMachines(s);
        PhysicalMachines = Racks.SelectMany(d => d.PhysicalMachines).ToList();

        for (int i = 0; i < k; i++)
        {
            nums = ReadInts();
            foreach (PhysicalMachine physicalMachine in PhysicalMachines)
                physicalMachine.Nodes.Add(new NumaNode { ID = i + 1, MaxCPU = nums[0], MaxRAM = nums[1], PhysicalMachine = physicalMachine });
        }

        int f = ReadInt();
        for (int i = 0; i < f; i++)
        {
            nums = ReadInts();
            VirtualMachinesTypes.Add(new VirtualMachine { NumaCount = nums[0], CPU = nums[1], RAM = nums[2] });
        }
        VirtualMachinesDoubles = VirtualMachinesTypes.Where(t => t.NumaCount > 1).ToList();

        Stopwatch sw = Stopwatch.StartNew();
        int maxCPU = PhysicalMachines[0].Nodes.Sum(n => n.MaxCPU);
        int maxRAM = PhysicalMachines[0].Nodes.Sum(n => n.MaxRAM);
        bool[,] vmReachable = new bool[maxCPU + 1, maxRAM + 1];
        FindReachable(vmReachable, 0, 0, maxCPU, maxRAM, 0);
        NumaNode.Score = new double[maxCPU + 1, maxRAM + 1];
        NumaNode.ScoreSingle = new double[maxCPU + 1, maxRAM + 1];
        for (int cpu = 0; cpu <= maxCPU; cpu++)
        {
            for (int ram = 0; ram <= maxRAM; ram++)
            {
                foreach (VirtualMachine machine in VirtualMachinesTypes)
                {
                    int maxMachines = Math.Min(maxCPU / machine.CPU, maxRAM / machine.RAM);
                    int currentMachines = Math.Min(Math.Max(1, cpu) / machine.CPU, Math.Max(1, ram) / machine.RAM);
                    NumaNode.Score[cpu, ram] += (double)currentMachines / maxMachines;
                    if (machine.NumaCount == 1) NumaNode.ScoreSingle[cpu, ram] += (double)currentMachines / maxMachines;
                }
            }
        }

        while (true)
        {
            InstructionType instruction = (InstructionType)ReadInt();
            if (instruction == InstructionType.Terminate) return;
            if (instruction == InstructionType.PlacementGroupCreate)
            {
                nums = ReadInts();
                int j = nums[0], kj = nums[1], aj = nums[2];
                nums = ReadInts();
                int nj = nums[0], rj = nums[1];
                PlacementGroup group = new PlacementGroup(j, kj, aj, nj, rj);
                PlacementGroups[group.ID] = group;
            }
            if (instruction == InstructionType.VirtualMachineCreate)
            {
#if !DEBUG
                if (!FastMode && sw.ElapsedMilliseconds > 9000) FastMode = true;
#endif
                nums = ReadInts();
                int li = nums[0], fi = nums[1], ji = nums[2], pi = nums[3];
                int[] vmIndices = ReadInts();

                VirtualMachineCreateInstruction create = new VirtualMachineCreateInstruction(li, VirtualMachinesTypes[fi - 1], PlacementGroups[ji], pi, vmIndices);
                if (!create.Create())
                    return;
            }
            if (instruction == InstructionType.VirtualMachineDelete)
            {
                nums = ReadInts();
                foreach (int num in nums.Skip(1))
                {
                    VirtualMachines[num].Delete();
                    VirtualMachines.Remove(num);
                }
            }

#if DEBUG
            int cpuUsePhysical = PhysicalMachines.SelectMany(p => p.Nodes).Sum(n => n.CurrentCPU);
            int virtualCPU = VirtualMachines.Values.Sum(v => v.CPU * v.NumaCount);
            if (cpuUsePhysical != virtualCPU) Debugger.Break();
#endif
        }
    }

    private static void FindReachable(bool[,] vmReachable, int cpu, int ram, int maxCPU, int maxRAM, int vmIndex)
    {
        if (vmReachable[cpu, ram] || vmIndex == VirtualMachinesTypes.Count) return;
        vmReachable[cpu, ram] = true;
        for (int uses = 1; ; uses++)
        {
            int _cpu = cpu + uses * VirtualMachinesTypes[vmIndex].CPU;
            int _ram = ram + uses * VirtualMachinesTypes[vmIndex].RAM;
            if (_ram > maxRAM || _cpu > maxCPU) break;
            FindReachable(vmReachable, _cpu, _ram, maxCPU, maxRAM, vmIndex + 1);
        }
    }
}