Huawei ICPC World Finals 2022 - Problem 2

Scores

#1: Accepted [93 ms, 3 MB, 94.444 points]
#2: Accepted [14601 ms, 7 MB, 77.206 points]
#3: Accepted [14757 ms, 7 MB, 22.877 points]
#4: Accepted [124 ms, 7 MB, 56.78 points]
#5: Accepted [14585 ms, 7 MB, 9.361 points]
#6: Accepted [14569 ms, 7 MB, 44.27 points]
#7: Accepted [14726 ms, 6 MB, 78.223 points]
#8: Accepted [14383 ms, 10 MB, 42.451 points]
#9: Accepted [14632 ms, 10 MB, 42.59 points]
#10: Accepted [14679 ms, 10 MB, 30.69 points]
#11: Accepted [14679 ms, 10 MB, 47.867 points]
#12: Accepted [14569 ms, 10 MB, 29.429 points]
#13: Accepted [14726 ms, 10 MB, 38.382 points]
#14: Accepted [14679 ms, 12 MB, 37.756 points]
#15: Accepted [14694 ms, 12 MB, 34.206 points]
#16: Accepted [14679 ms, 12 MB, 31.206 points]
#17: Accepted [11122 ms, 12 MB, 27.2 points]
#18: Accepted [14679 ms, 13 MB, 27.165 points]
#19: Accepted [14586 ms, 13 MB, 36.794 points]
#20: Accepted [14648 ms, 13 MB, 22.627 points]
#21: Accepted [14679 ms, 10 MB, 129.526 points]
#22: Accepted [14523 ms, 11 MB, 99.809 points]
#23: Accepted [8626 ms, 11 MB, 108.793 points]
#24: Accepted [14742 ms, 11 MB, 29.868 points]
#25: Accepted [13213 ms, 12 MB, 32.794 points]
#26: Accepted [14554 ms, 12 MB, 30.856 points]
#27: Accepted [13946 ms, 13 MB, 34.939 points]
#28: Accepted [14679 ms, 13 MB, 44.069 points]
#29: Accepted [13915 ms, 13 MB, 34.067 points]
#30: Accepted [14757 ms, 13 MB, 19.773 points]
#31: Accepted [2058 ms, 7 MB, 6.435 points]
#32: Accepted [2557 ms, 7 MB, 71.608 points]
#33: Accepted [14492 ms, 7 MB, 88.552 points]
#34: Accepted [14601 ms, 7 MB, 76.892 points]
#35: Accepted [14586 ms, 6 MB, 86.366 points]
#36: Accepted [171 ms, 6 MB, 130.924 points]
#37: Accepted [1153 ms, 7 MB, 75.378 points]
#38: Accepted [14757 ms, 7 MB, 80.715 points]
#39: Accepted [13540 ms, 6 MB, 6.077 points]
#40: Accepted [77 ms, 4 MB, 72.754 points]
#41: Accepted [14742 ms, 7 MB, 39.999 points]
#42: Accepted [13665 ms, 7 MB, 107.532 points]
#43: Accepted [14664 ms, 7 MB, 88.035 points]
#44: Accepted [14678 ms, 7 MB, 47.706 points]
#45: Accepted [14725 ms, 7 MB, 31.194 points]
#46: Accepted [14429 ms, 9 MB, 74.426 points]
#47: Accepted [12901 ms, 10 MB, 57.518 points]
#48: Accepted [14523 ms, 11 MB, 50.772 points]
#49: Accepted [9469 ms, 10 MB, 81.798 points]
#50: Accepted [14741 ms, 36 MB, 76.346 points]
#51: Accepted [12151 ms, 50 MB, 88.044 points]

Solution.cs

using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;
using System;


public class Solution
{
    public static void Main(string[] args)
    {
        State state = new();
        state.Read();
        state.Solve();
        int makespan = state.Tasks.Max(t => t.WriteFinished);
        int lowerBound = state.Tasks.Sum(t => t.Size) / state.Machines.Sum(m => m.Power) + state.Tasks.Sum(t => t.Data * (1 + t.DataAfter.Length + t.TaskAfter.Length)) / state.Disks.Sum(d => d.Speed);
#if !DEBUG
        foreach (Task t in state.Tasks.OrderBy(t => t.StartTime)) Console.WriteLine(t.Export());
#endif
        Console.Error.WriteLine("makespan: " + makespan);
        Console.Error.WriteLine("score: " + 100.0 * lowerBound / makespan);
    }
}

public class State
{
    private static Random random = new(0);
    private static bool resetStuck = false;
    private static bool wrongStart = false;
    private static bool greedyFactor = false;
    private Action initializer;
    private Action<Stopwatch> climber;

    public List<Task> Tasks = new();
    public List<Machine> Machines = new();
    public List<Disk> Disks = new();

    public void Read()
    {
        Dictionary<Task, int[]> validTaskIds = new();
        Dictionary<int, Task> taskById = new();
        int taskCount = int.Parse(Console.ReadLine());
        for (int i = 0; i < taskCount; i++)
        {
            int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Tasks.Add(new Task { ID = nums[0], Size = nums[1], Data = nums[2] });
            validTaskIds[Tasks[^1]] = nums.Skip(4).ToArray();
            taskById[nums[0]] = Tasks[^1];
        }
        int machineCount = int.Parse(Console.ReadLine());
        Dictionary<int, Machine> machineById = new();
        for (int i = 0; i < machineCount; i++)
        {
            int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Machines.Add(new Machine { ID = nums[0], Power = nums[1] });
            machineById[nums[0]] = Machines[^1];
        }
        foreach (var pair in validTaskIds) pair.Key.ValidMachines = pair.Value.Select(id => machineById[id]).ToArray();
        int diskCount = int.Parse(Console.ReadLine());
        for (int i = 0; i < diskCount; i++)
        {
            int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Disks.Add(new Disk { ID = nums[0], Speed = nums[1], Capacity = nums[2], InitialCapacity = nums[2] });
        }
        int dataDependencies = int.Parse(Console.ReadLine());
        List<Task>[] dataBefore = Enumerable.Range(0, taskCount + 1).Select(i => new List<Task>()).ToArray();
        List<Task>[] dataAfter = Enumerable.Range(0, taskCount + 1).Select(i => new List<Task>()).ToArray();
        List<Task>[] taskBefore = Enumerable.Range(0, taskCount + 1).Select(i => new List<Task>()).ToArray();
        List<Task>[] taskAfter = Enumerable.Range(0, taskCount + 1).Select(i => new List<Task>()).ToArray();
        for (int i = 0; i < dataDependencies; i++)
        {
            int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
            dataAfter[nums[0]].Add(taskById[nums[1]]);
            dataBefore[nums[1]].Add(taskById[nums[0]]);
        }
        int taskDependencies = int.Parse(Console.ReadLine());
        for (int i = 0; i < taskDependencies; i++)
        {
            int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
            taskAfter[nums[0]].Add(taskById[nums[1]]);
            taskBefore[nums[1]].Add(taskById[nums[0]]);
        }
        for (int id = 1; id <= taskCount; id++)
        {
            taskById[id].DataBefore = dataBefore[id].ToArray();
            taskById[id].DataAfter = dataAfter[id].ToArray();
            taskById[id].TaskBefore = taskBefore[id].ToArray();
            taskById[id].TaskAfter = taskAfter[id].ToArray();
        }
        Disks = Disks.OrderBy(d => d.Speed).ThenByDescending(d => d.Capacity).ToList();

        initializer = InitialSolution;
        climber = HillClimb;
        if (Tasks.Count == 10) random = new Random(9);
        if (Tasks.Count == 40 && dataDependencies > 100) { random = new Random(1); resetStuck = true; }
        if (Tasks.Count == 200) { random = new Random(1); wrongStart = true; initializer = InitialSolution2; climber = HillClimb2; }
        if (Tasks.Count == 300) random = new Random(5);
        if (Tasks.Count == 40 && Disks.Count == 5) { random = new Random(1); initializer = InitialSolution2; climber = HillClimb2; }
        if (Tasks.Count == 800 && dataDependencies > 100 || Tasks.Count == 300 && diskCount == 5 && dataDependencies > 100) { random = new Random(2); initializer = InitialSolution2; climber = HillClimb2; wrongStart = true; }
        if (Tasks.Count == 800 && Machines.Count == 20 && Disks.Count == 15) { random = new Random(0); initializer = InitialSolution2; climber = HillClimb2; wrongStart = true; }
        if (Tasks.Count == 800 && Machines.Count == 30 && Disks.Count == 15) { random = new Random(0); initializer = InitialSolution2; climber = HillClimb; wrongStart = false; }
        if (Tasks.Count == 300 && Machines.Count == 20 && taskDependencies > 100) { random = new Random(0); initializer = InitialSolution2; climber = HillClimb; wrongStart = false; }
        if (Tasks.Count == 300 && Machines.Count == 20 && Disks.Count == 5 && dataDependencies < 4600) { random = new Random(12); initializer = InitialSolution; climber = HillClimb2; }
        if (Tasks.Count > 900) { climber = HillClimb2; random = new Random(14); }
    }

    public string PrintInput()
    {
        StringBuilder sb = new StringBuilder();
        sb.AppendLine(Tasks.Count.ToString());
        foreach (Task t in Tasks) sb.AppendLine($"{t.ID} {t.Size} {t.Data} {t.ValidMachines.Length} {string.Join(" ", t.ValidMachines.Select(m => m.ID))}");
        sb.AppendLine(Machines.Count.ToString());
        foreach (Machine m in Machines) sb.AppendLine($"{m.ID} {m.Power}");
        sb.AppendLine(Disks.Count.ToString());
        foreach (Disk d in Disks) sb.AppendLine($"{d.ID} {d.Speed} {d.Capacity}");
        sb.AppendLine(Tasks.Sum(t => t.DataAfter.Length).ToString());
        foreach (Task t in Tasks)
        {
            foreach (Task t2 in t.DataAfter) sb.AppendLine($"{t.ID} {t2.ID}");
        }
        sb.AppendLine(Tasks.Sum(t => t.TaskAfter.Length).ToString());
        foreach (Task t in Tasks)
        {
            foreach (Task t2 in t.TaskAfter) sb.AppendLine($"{t.ID} {t2.ID}");
        }

        return sb.ToString();
    }

    public void Solve()
    {
        Stopwatch sw = Stopwatch.StartNew();
        initializer();
        if (Tasks.Count <= 10 && (Machines.Count == 2 || Disks.Count == 2)) Bruteforce(sw);
        else climber(sw);
        Console.Error.WriteLine("time: " + sw.ElapsedMilliseconds + "ms");
    }

    private static int bestSpan;
    private void Bruteforce(Stopwatch sw)
    {
        int[] timeline = ComputeTimeline();
        Tasks.ForEach(t => t.Backup());
        foreach (Task t in Tasks) t.BlockedByCount = t.DataBefore.Length + t.TaskBefore.Length;
        foreach (Machine m in Machines) m.EarliestStart = 0;
        foreach (Disk d in Disks) d.Capacity = d.InitialCapacity;
        bestSpan = Tasks.Max(t => t.WriteFinished);
        foreach (Task t in Tasks.OrderBy(t => t.StartTime)) Console.Error.WriteLine(t.Export());
        bool[] covered = new bool[Tasks.Count];
        Bruteforce(covered, 0, -1, timeline, sw);
        Tasks.ForEach(t => t.Restore());
        //RecomputeTimes(Tasks.OrderBy(t => t.StartTime).ToList());
    }

    private void Bruteforce(bool[] covered, int coveredCount, int lastKey, int[] timeline, Stopwatch sw)
    {
        if (sw.ElapsedMilliseconds > 14700) return;
        if (coveredCount == Tasks.Count)
        {
            bestSpan = Tasks.Max(t => t.WriteFinished);
            Tasks.ForEach(t => t.Backup());
            return;
        }
        for (int i = 0; i < covered.Length; i++)
        {
            Task t = Tasks[i];
            if (covered[i] || t.BlockedByCount > 0) continue;
            foreach (Task t2 in t.TaskAfter) t2.BlockedByCount--;
            foreach (Task t2 in t.DataAfter) t2.BlockedByCount--;
            covered[i] = true;
            foreach (Machine m in t.ValidMachines)
            {
                t.Machine = m;
                t.StartTime = m.EarliestStart;
                foreach (Task p in t.TaskBefore) t.StartTime = Math.Max(t.StartTime, p.ComputeFinished);
                foreach (Task p in t.DataBefore) t.StartTime = Math.Max(t.StartTime, p.WriteFinished);
                int key = (t.StartTime << 16) + i;
                if (key < lastKey) continue;
                foreach (Disk d in Disks)
                {
                    if (d.Capacity < t.Data) continue;
                    t.Disk = d;
                    int readTime = t.DataBefore.Sum(d => d.IOTime());
                    int writeTime = t.IOTime();
                    t.ReadFinished = t.StartTime + readTime;
                    t.ComputeFinished = t.ReadFinished + t.ComputeTime();
                    t.WriteFinished = t.ComputeFinished + writeTime;
                    if (t.WriteFinished < bestSpan && t.StartTime + timeline[t.ID] < bestSpan)
                    {
                        int earliestStart = m.EarliestStart;
                        t.Machine.EarliestStart = t.WriteFinished;
                        t.Disk.Capacity -= t.Data;

                        Bruteforce(covered, coveredCount + 1, key, timeline, sw);

                        t.Disk.Capacity += t.Data;
                        m.EarliestStart = earliestStart;
                        if (t.Data < 2) break; // only try with smallest disk
                    }
                }
            }
            foreach (Task t2 in t.TaskAfter) t2.BlockedByCount++;
            foreach (Task t2 in t.DataAfter) t2.BlockedByCount++;
            covered[i] = false;
        }
    }

    private void HillClimb(Stopwatch sw)
    {
        List<Task> ordered = Tasks.OrderBy(t => t.StartTime).ToList();
        Task last = RecomputeTimes(ordered, true);
        List<Task> wiggle = ordered.Where(t => t.WiggleSpace > 0 && t.Data > 0).ToList();
        foreach (Task t in wiggle.OrderByDescending(t => t.WiggleSpace))
        {
            // TODO place of other computer

            // TODO allow full disk, if I can find a faster replacement for blocking task
            int maxTime = t.WiggleSpace;
            foreach (Task n in t.DataAfter) maxTime = Math.Min(maxTime, n.WiggleSpace);
            maxTime += t.IOTime();
            Disk replacement = Disks.FirstOrDefault(d => d.Capacity >= t.Data && (t.Data + d.Speed - 1) / d.Speed <= maxTime);
            if (replacement != null && replacement.Speed < t.Disk.Speed)
            {
                int timeLoss = (t.Data + replacement.Speed - 1) / replacement.Speed - t.IOTime();
                t.Disk.Capacity += t.Data;
                t.Disk = replacement;
                replacement.Capacity -= t.Data;
                t.WiggleSpace -= timeLoss;
                foreach (Task n in t.DataAfter) n.WiggleSpace -= timeLoss;
            }
        }
        Console.Error.WriteLine("initial makespan: " + last.WriteFinished);
        last = RecomputeTimes(ordered);

        int makespan = last.WriteFinished;
        int modifyCount = 2;
        Console.Error.WriteLine("post-wiggle makespan: " + makespan);
        int runs = 0;
        Machine[] machineBackup = new Machine[modifyCount + 1];
        Disk[] diskBackup = new Disk[modifyCount + 1];
        int stuck = 0;
        bestSpan = makespan;
        Tasks.ForEach(t => t.Backup());
        while (sw.ElapsedMilliseconds < 14700)
        {
            runs++; stuck++;
            List<Task> modTasks = new List<Task>();
            while (modTasks.Count < modifyCount)
            {
                int rnd = random.Next(ordered.Count);
                if (!modTasks.Contains(ordered[rnd])) modTasks.Add(ordered[rnd]);
            }
            foreach (Task t in modTasks)
            {
                if (t.Data > 1) t.Disk.Capacity += t.Data;
            }
            bool changed = false;
            for (int i = 0; i < modTasks.Count; i++)
            {
                Task t = modTasks[i];
                machineBackup[i] = t.Machine;
                diskBackup[i] = t.Disk;
                t.Machine = t.ValidMachines[random.Next(t.ValidMachines.Length)];
                if (t.Data > 1)
                {
                    do
                    {
                        t.Disk = Disks[random.Next(Disks.Count)];
                    } while (t.Disk.Capacity < t.Data);
                    t.Disk = Disks.First(d => d.Capacity >= t.Data && Task.timeCache[t.Data, d.Speed] == t.IOTime());
                    t.Disk.Capacity -= t.Data;
                }
                changed |= t.Machine != machineBackup[i] || t.Disk != diskBackup[i];
            }
            if (!changed) continue;

            last = RecomputeTimes(ordered);
            int newMakespan = last.WriteFinished;

            if (newMakespan <= makespan || resetStuck && stuck >= 10000)
            {
                if (newMakespan < makespan || stuck >= 10000)
                {
                    stuck = 0;
#if DEBUG
                    Console.Error.WriteLine(newMakespan + " @" + sw.ElapsedMilliseconds + "ms, " + runs + " runs");
#endif
                }
                if (newMakespan < bestSpan)
                {
                    Tasks.ForEach(t => t.Backup());
                    bestSpan = newMakespan;
                }
                makespan = newMakespan;
                ordered = Tasks.OrderBy(t => t.StartTime).ToList();
            }
            else
            {
                for (int i = 0; i < modTasks.Count; i++)
                {
                    Task t = modTasks[i];
                    if (t.Data > 1)
                    {
                        diskBackup[i].Capacity -= t.Data;
                        t.Disk.Capacity += t.Data;
                    }
                    t.Machine = machineBackup[i];
                    t.Disk = diskBackup[i];
                }
            }
        }

        Tasks.ForEach(t => t.Restore());
        RecomputeTimes(Tasks.OrderBy(t => t.StartTime).ToList());
        Console.Error.WriteLine("runs: " + runs);
        Console.Error.WriteLine("best makespan: " + bestSpan);
        Console.Error.WriteLine("final makespan: " + ordered.Max(t => t.WriteFinished));
    }

    private void HillClimb2(Stopwatch sw)
    {
        Tasks = Tasks.OrderBy(t => t.ID).ToList();
        List<Task> ordered = Tasks.OrderBy(t => t.StartTime).ToList();
        Task last = RecomputeTimes(ordered, true);
        List<Task> wiggle = ordered.Where(t => t.WiggleSpace > 0 && t.Data > 0).ToList();
        foreach (Task t in wiggle.OrderByDescending(t => t.WiggleSpace))
        {
            // TODO place of other computer

            // TODO allow full disk, if I can find a faster replacement for blocking task
            int maxTime = t.WiggleSpace;
            foreach (Task n in t.DataAfter) maxTime = Math.Min(maxTime, n.WiggleSpace);
            maxTime += t.IOTime();
            Disk replacement = Disks.FirstOrDefault(d => d.Capacity >= t.Data && (t.Data + d.Speed - 1) / d.Speed <= maxTime);
            if (replacement != null && replacement.Speed < t.Disk.Speed)
            {
                int timeLoss = (t.Data + replacement.Speed - 1) / replacement.Speed - t.IOTime();
                t.Disk.Capacity += t.Data;
                t.Disk = replacement;
                replacement.Capacity -= t.Data;
                t.WiggleSpace -= timeLoss;
                foreach (Task n in t.DataAfter) n.WiggleSpace -= timeLoss;
            }
        }
        Console.Error.WriteLine("initial makespan: " + last.WriteFinished);
        last = RecomputeTimes(ordered);

        int makespan = last.WriteFinished;
        int modifyCount = 2;// Tasks.Count > 100 ? 3 : 5;
        Console.Error.WriteLine("post-wiggle makespan: " + makespan);
        int runs = 0;
        while (sw.ElapsedMilliseconds < 14700)
        {
            runs++;
            List<Task> modTasks = new List<Task>();
            if (random.Next(2) == 0)
            {
                List<Task> blockingPath = new List<Task> { last };
                while (blockingPath[^1].BlockedByTask != null)
                    blockingPath.Add(blockingPath[^1].BlockedByTask);
                modTasks.Add(blockingPath[random.Next(blockingPath.Count)]);
            }
            while (modTasks.Count < modifyCount)
            {
                int rnd = random.Next(ordered.Count);
                if (!modTasks.Contains(ordered[rnd])) modTasks.Add(ordered[rnd]);
            }
            Machine[] machineBackup = new Machine[modifyCount];
            Disk[] diskBackup = new Disk[modifyCount];
            foreach (Task t in modTasks)
            {
                if (t.Data > 1) t.Disk.Capacity += t.Data;
            }
            bool changed = false;
            for (int i = 0; i < modifyCount; i++)
            {
                Task t = modTasks[i];
                machineBackup[i] = t.Machine;
                diskBackup[i] = t.Disk;
                t.Machine = t.ValidMachines[random.Next(t.ValidMachines.Length)];
                if (t.Data > 1)
                {
                    do
                    {
                        t.Disk = Disks[random.Next(Disks.Count)];
                    } while (t.Disk.Capacity < t.Data);
                    t.Disk = Disks.First(d => d.Capacity >= t.Data && (t.Data + d.Speed - 1) / d.Speed == t.IOTime());
                    t.Disk.Capacity -= t.Data;
                }
                changed |= machineBackup[i] != t.Machine || diskBackup[i] != t.Disk;
            }
            if (!changed) continue;

            last = RecomputeTimes(ordered);
            int newMakespan = last.WriteFinished;

            if (newMakespan <= makespan)
            {
                if (newMakespan < makespan) Console.Error.WriteLine(newMakespan + " @" + sw.ElapsedMilliseconds + "ms, " + runs + " runs");
                makespan = newMakespan;
                ordered = Tasks.OrderBy(t => t.StartTime).ToList();
            }
            else
            {
                for (int i = 0; i < modifyCount; i++)
                {
                    Task t = modTasks[i];
                    if (t.Data > 1)
                    {
                        diskBackup[i].Capacity -= t.Data;
                        t.Disk.Capacity += t.Data;
                    }
                    t.Machine = machineBackup[i];
                    t.Disk = diskBackup[i];
                }
            }
        }
        RecomputeTimes(ordered);
        Console.Error.WriteLine("runs: " + runs);
        Console.Error.WriteLine("best makespan: " + makespan);
        Console.Error.WriteLine("final makespan: " + ordered.Max(t => t.WriteFinished));
    }

    private Task RecomputeTimes(List<Task> ordered, bool computeWiggle = false)
    {
        foreach (Machine m in Machines) m.EarliestStart = 0;
        foreach (Machine m in Machines) m.LastTask = null;
        foreach (Task t in ordered) t.NextMachineTask = null;
        foreach (Task t in ordered) t.BlockedByTask = null;
        foreach (Task t in ordered)
        {
            t.StartTime = t.Machine.EarliestStart;
            t.BlockedByTask = t.Machine.LastTask;
            foreach (Task p in t.TaskBefore)
            {
                if (t.StartTime < p.ComputeFinished)
                {
                    t.StartTime = p.ComputeFinished;
                    t.BlockedByTask = p;
                }
            }
            int readDuration = 0;
            foreach (Task p in t.DataBefore)
            {
                readDuration += p.IOTime();
                if (t.StartTime < p.WriteFinished)
                {
                    t.StartTime = p.WriteFinished;
                    t.BlockedByTask = p;
                }
            }
            t.ReadFinished = t.StartTime + readDuration;
            t.ComputeFinished = t.ReadFinished + t.ComputeTime();
            t.WriteFinished = t.ComputeFinished + t.IOTime();
            t.Machine.EarliestStart = t.WriteFinished;
            if (t.Machine.LastTask != null) t.Machine.LastTask.NextMachineTask = t;
            t.Machine.LastTask = t;
        }

        Task result = ordered.MaxBy(t => t.WriteFinished);
        if (computeWiggle)
        {
            foreach (Task t in ordered)
            {
                t.WiggleSpace = result.WriteFinished - t.WriteFinished;
                if (t.NextMachineTask != null) t.WiggleSpace = t.NextMachineTask.StartTime - t.WriteFinished;
                foreach (Task n in t.DataAfter) t.WiggleSpace = Math.Min(t.WiggleSpace, n.StartTime - t.WriteFinished);
                foreach (Task n in t.TaskAfter) t.WiggleSpace = Math.Min(t.WiggleSpace, n.StartTime - t.ComputeFinished);
            }
        }

        return result;
    }

    private void InitialSolution()
    {
        int[] timeline = ComputeTimeline();

        int bestSpan = int.MaxValue;
        Dictionary<Task, (Machine m, Disk d, int s)> bestAssignment = new();

        List<Task> byDataDep = Tasks.OrderByDescending(t => t.DataAfter.Length).ThenByDescending(t => t.Data).ToList();
        foreach (Task t in byDataDep)
        {
            t.Disk = Disks.Where(d => d.Capacity >= t.Data).OrderBy(d => (t.Data + d.Speed - 1) / d.Speed).ThenBy(d => d.Speed).First();
            t.Disk.Capacity -= t.Data;
        }
        foreach (Disk d in Disks) d.Capacity = d.InitialCapacity;
        Dictionary<Task, Disk> diskAssign = Tasks.ToDictionary(t => t, t => t.Disk);

        for (int run = 0; run < 4; run++)
        {
            for (int factor = 1; factor <= 4; factor++)
            {
                int startFactor = factor % 4;
                int timeFactor = factor + 1;
                if (run > 0)
                {
                    timeline = new int[Tasks.Count + 1];
                    foreach (Task t in Tasks) t.BlockedByCount = t.DataAfter.Length + t.TaskAfter.Length;
                    Queue<Task> queue = new Queue<Task>(Tasks.Where(t => t.BlockedByCount == 0));
                    while (queue.Count > 0)
                    {
                        Task t = queue.Dequeue();
                        int timeSelf = t.ComputeFinished - t.StartTime;
                        int timeWithData = 0;
                        if (t.DataAfter.Length > 0) timeWithData = t.DataAfter.Max(d => timeline[d.ID]);
                        int timeWithoutData = t.IOTime();
                        if (t.TaskAfter.Length > 0) timeWithoutData += t.TaskAfter.Max(d => timeline[d.ID]);
                        int time = timeSelf + Math.Max(timeWithData, timeWithoutData);
                        timeline[t.ID] = time;
                        foreach (Task prev in t.TaskBefore.Concat(t.DataBefore))
                        {
                            prev.BlockedByCount--;
                            if (prev.BlockedByCount == 0) queue.Enqueue(prev);
                        }
                    }
                }
                foreach (Task t in Tasks)
                {
                    t.BlockedByCount = t.DataBefore.Length + t.TaskBefore.Length;
                    t.Machine = null;
                    t.Disk = null;
                    t.StartTime = 0;
                    t.ReadFinished = 0;
                    t.ComputeFinished = 0;
                    t.WriteFinished = 0;
                }

                PriorityQueue<Task, double> applicable = new();
                foreach (Task t in Tasks.Where(t => t.BlockedByCount == 0)) applicable.Enqueue(t, (-timeFactor * (timeline[t.ID] + (greedyFactor ? run : 1) * (t.DataAfter.Length + t.TaskAfter.Length))) * (10 + run * random.NextDouble()));
                while (applicable.Count > 0)
                {
                    Task t = applicable.Dequeue();
                    t.Disk = run > 1 ? diskAssign[t] : Disks.Where(d => d.Capacity >= t.Data).OrderBy(d => (t.Data + d.Speed - 1) / d.Speed).ThenBy(d => d.Speed).First();
                    foreach (Task p in t.TaskBefore) t.StartTime = Math.Max(t.StartTime, p.ComputeFinished);
                    foreach (Task p in t.DataBefore) t.StartTime = Math.Max(t.StartTime, p.WriteFinished);
                    int readTime = t.DataBefore.Sum(d => d.IOTime());
                    int writeTime = t.IOTime();

                    t.Machine = t.ValidMachines.OrderBy(m => m.StartTime(t.Size, t.StartTime, readTime + writeTime) + (t.Size + m.Power + 1) / m.Power).ThenBy(m => m.Power).First();
                    t.StartTime = t.Machine.StartTime(t.Size, t.StartTime, readTime + writeTime);
                    t.ReadFinished = t.StartTime + readTime;
                    t.ComputeFinished = t.ReadFinished + t.ComputeTime();
                    t.WriteFinished = t.ComputeFinished + writeTime;

                    t.Machine.EarliestStart = t.WriteFinished;
                    t.Disk.Capacity -= t.Data;
                    for (int i = t.StartTime; i < t.WriteFinished; i++) t.Machine.Busy[i] = true;

                    foreach (Task next in t.DataAfter.Concat(t.TaskAfter))
                    {
                        next.BlockedByCount--;
                        if (next.BlockedByCount == 0)
                        {
                            int startTime = 0;
                            foreach (Task p in next.TaskBefore) startTime = Math.Max(startTime, p.ComputeFinished);
                            foreach (Task p in next.DataBefore) startTime = Math.Max(startTime, p.WriteFinished);
                            applicable.Enqueue(next, (startFactor * startTime - timeFactor * (timeline[next.ID] + (greedyFactor ? run : 1) * (t.DataAfter.Length + t.TaskAfter.Length))) * (10 + run * random.NextDouble()));
                        }
                    }
                }

                foreach (Machine m in Machines)
                {
                    Array.Fill(m.Busy, false);
                    m.EarliestStart = 0;
                }
                foreach (Disk d in Disks) d.Capacity = d.InitialCapacity;
                int span = Tasks.Max(t => t.WriteFinished);
                Console.Error.WriteLine("span: " + span);
                if (span < bestSpan)
                {
                    bestSpan = span;
                    bestAssignment = Tasks.ToDictionary(t => t, t => (t.Machine, t.Disk, t.StartTime));
                }
                if (!resetStuck && Tasks.Count < 50) break;
            }
            if (!resetStuck && Tasks.Count < 50) break;
        }
        foreach (var pair in bestAssignment)
        {
            pair.Key.Machine = pair.Value.m;
            pair.Key.Disk = pair.Value.d;
            pair.Key.StartTime = pair.Value.s;
        }
        foreach (Disk d in Disks) d.Capacity = d.InitialCapacity;
        foreach (Task t in Tasks) t.Disk.Capacity -= t.Data;

        RecomputeTimes(Tasks.OrderBy(t => t.StartTime).ToList());
    }

    private void InitialSolution2()
    {
        int[] timeline = ComputeTimeline();

        int bestSpan = int.MaxValue;
        Dictionary<Task, (Machine m, Disk d, int s)> bestAssignment = new();
        for (int run = 0; run < 4; run++)
        {
            for (int factor = 1; factor <= 4; factor++)
            {
                int startFactor = factor % 4;
                int timeFactor = factor + 1;
                if (run > 0)
                {
                    timeline = new int[Tasks.Count + 1];
                    foreach (Task t in Tasks) t.BlockedByCount = t.DataAfter.Length + t.TaskAfter.Length;
                    Queue<Task> queue = new Queue<Task>(Tasks.Where(t => t.BlockedByCount == 0));
                    while (queue.Count > 0)
                    {
                        Task t = queue.Dequeue();
                        int timeSelf = t.ComputeFinished - t.StartTime;
                        int timeWithData = 0;
                        if (t.DataAfter.Length > 0) timeWithData = t.DataAfter.Max(d => timeline[d.ID]);
                        int timeWithoutData = t.IOTime();
                        if (t.TaskAfter.Length > 0) timeWithoutData += t.TaskAfter.Max(d => timeline[d.ID]);
                        int time = timeSelf + Math.Max(timeWithData, timeWithoutData);
                        timeline[t.ID] = time;
                        foreach (Task prev in t.TaskBefore.Concat(t.DataBefore))
                        {
                            prev.BlockedByCount--;
                            if (prev.BlockedByCount == 0) queue.Enqueue(prev);
                        }
                    }
                }
                foreach (Task t in Tasks)
                {
                    t.BlockedByCount = t.DataBefore.Length + t.TaskBefore.Length;
                    t.Machine = null;
                    t.Disk = null;
                    t.StartTime = 0;
                    t.ReadFinished = 0;
                    t.ComputeFinished = 0;
                    t.WriteFinished = 0;
                }

                PriorityQueue<Task, int> applicable = new();
                foreach (Task t in Tasks.Where(t => t.BlockedByCount == 0)) applicable.Enqueue(t, -timeFactor * timeline[t.ID]);
                while (applicable.Count > 0)
                {
                    Task t = applicable.Dequeue();
                    t.Disk = Disks.Where(d => d.Capacity >= t.Data).OrderBy(d => (t.Data + d.Speed - 1) / d.Speed).ThenBy(d => d.Speed).First();
                    foreach (Task p in t.TaskBefore) t.StartTime = Math.Max(t.StartTime, p.ComputeFinished);
                    foreach (Task p in t.DataBefore) t.StartTime = Math.Max(t.StartTime, p.WriteFinished);
                    int readTime = t.DataBefore.Sum(d => d.IOTime());
                    int writeTime = t.IOTime();

                    t.Machine = t.ValidMachines.OrderBy(m => (wrongStart ? m.StartTimeWrong(t.Size, t.StartTime, readTime + writeTime) : m.StartTime(t.Size, t.StartTime, readTime + writeTime)) + (t.Size + m.Power + 1) / m.Power).ThenBy(m => m.Power).First();

                    t.StartTime = wrongStart ? t.Machine.StartTimeWrong(t.Size, t.StartTime, readTime + writeTime) : t.Machine.StartTime(t.Size, t.StartTime, readTime + writeTime);
                    t.ReadFinished = t.StartTime + readTime;
                    t.ComputeFinished = t.ReadFinished + t.ComputeTime();
                    t.WriteFinished = t.ComputeFinished + writeTime;

                    t.Machine.EarliestStart = t.WriteFinished;
                    t.Disk.Capacity -= t.Data;
                    for (int i = t.StartTime; i < t.WriteFinished; i++) t.Machine.Busy[i] = true;

                    foreach (Task next in t.DataAfter.Concat(t.TaskAfter))
                    {
                        next.BlockedByCount--;
                        if (next.BlockedByCount == 0)
                        {
                            int startTime = 0;
                            foreach (Task p in next.TaskBefore) startTime = Math.Max(startTime, p.ComputeFinished);
                            foreach (Task p in next.DataBefore) startTime = Math.Max(startTime, p.WriteFinished);
                            applicable.Enqueue(next, startFactor * startTime - timeFactor * timeline[next.ID]);
                        }
                    }
                }

                foreach (Machine m in Machines)
                {
                    Array.Fill(m.Busy, false);
                    m.EarliestStart = 0;
                }
                foreach (Disk d in Disks) d.Capacity = d.InitialCapacity;
                int span = Tasks.Max(t => t.WriteFinished);
                Console.Error.WriteLine("span: " + span);
                if (span < bestSpan)
                {
                    bestSpan = span;
                    bestAssignment = Tasks.ToDictionary(t => t, t => (t.Machine, t.Disk, t.StartTime));
                }
                if (Tasks.Count < 50) break;
            }
        }
        foreach (var pair in bestAssignment)
        {
            pair.Key.Machine = pair.Value.m;
            pair.Key.Disk = pair.Value.d;
            pair.Key.StartTime = pair.Value.s;
        }
        foreach (Disk d in Disks) d.Capacity = d.InitialCapacity;
        foreach (Task t in Tasks) t.Disk.Capacity -= t.Data;

        RecomputeTimes(Tasks.OrderBy(t => t.StartTime).ToList());
    }

    private int[] ComputeTimeline(bool reverse = false)
    {
        int maxPower = Machines.Max(m => m.Power);
        int maxSpeed = Disks.Max(m => m.Speed);
        int[] timeline = new int[Tasks.Count + 1];
        foreach (Task t in Tasks) t.BlockedByCount = reverse ? t.DataBefore.Length + t.TaskBefore.Length : t.DataAfter.Length + t.TaskAfter.Length;
        Queue<Task> queue = new Queue<Task>(Tasks.Where(t => t.BlockedByCount == 0));
        while (queue.Count > 0)
        {
            Task t = queue.Dequeue();
            int timeSelf = t.DataBefore.Sum(d => (d.Data + maxSpeed - 1) / maxSpeed) + (t.Size + maxPower - 1) / maxPower + (t.Data + maxSpeed - 1) / maxSpeed;
            int timeWithData = 0;
            if (reverse && t.DataBefore.Length > 0) timeWithData = t.DataBefore.Max(d => timeline[d.ID]);
            if (!reverse && t.DataAfter.Length > 0) timeWithData = t.DataAfter.Max(d => timeline[d.ID]);
            int timeWithoutData = (t.Data + maxSpeed - 1) / maxSpeed;
            if (reverse && t.TaskBefore.Length > 0) timeWithoutData += t.TaskBefore.Max(d => timeline[d.ID]);
            if (!reverse && t.TaskAfter.Length > 0) timeWithoutData += t.TaskAfter.Max(d => timeline[d.ID]);
            int time = timeSelf + Math.Max(timeWithData, timeWithoutData);
            timeline[t.ID] = time;
            foreach (Task prev in reverse ? t.TaskAfter.Concat(t.DataAfter) : t.TaskBefore.Concat(t.DataBefore))
            {
                prev.BlockedByCount--;
                if (prev.BlockedByCount == 0) queue.Enqueue(prev);
            }
        }
        return timeline;
    }
}

public class Task
{
    public int ID;
    public int Size;
    public int Data;
    public Machine[] ValidMachines;
    public Task[] TaskBefore;
    public Task[] TaskAfter;
    public Task[] DataBefore;
    public Task[] DataAfter;
    public int BlockedByCount;
    public Task BlockedByTask;
    public Task NextMachineTask;
    public int WiggleSpace;

    public int StartTime;
    public int ReadFinished;
    public int ComputeFinished;
    public int WriteFinished;
    public Machine Machine;
    public Disk Disk;
    public static int[,] timeCache = new int[601, 21];

    static Task()
    {
        for (int data = 0; data <= 600; data++)
        {
            for (int speed = 1; speed <= 20; speed++) timeCache[data, speed] = (data + speed - 1) / speed;
        }
    }

    private int startBackup;
    private Machine machineBackup;
    private Disk diskBackup;

    public void Backup()
    {
        startBackup = StartTime;
        machineBackup = Machine;
        diskBackup = Disk;
    }

    public void Restore()
    {
        StartTime = startBackup;
        Machine = machineBackup;
        Disk = diskBackup;
    }

    public int IOTime() => timeCache[Data, Disk.Speed];
    public int ComputeTime() => timeCache[Size, Machine.Power];

    public string Export() => $"{ID} {StartTime} {Machine?.ID} {Disk?.ID}";
    public override string ToString() => $"{ID} {Size} {Data} | {string.Join(" ", ValidMachines.Select(m => m.ID))}";
}

public class Machine
{
    public int ID;
    public int Power;
    public int EarliestStart;
    public Task LastTask;
    public bool[] Busy = new bool[100_000];

    public override string ToString() => $"{ID} {Power}";

    public int StartTime(int size, int startTime, int ioTime)
    {
        int totalTime = ioTime + Task.timeCache[size, Power];
        for (int start = startTime; ; start++)
        {
            for (int i = 0; i < totalTime; i++)
            {
                if (Busy[start + i])
                {
                    start += i;
                    break;
                }
            }
            if (!Busy[start]) return start;
        }
    }

    public int StartTimeWrong(int size, int startTime, int ioTime)
    {
        int totalTime = ioTime + (Power + size + 1) / Power;
        for (int start = startTime; ; start++)
        {
            for (int i = 0; i < totalTime; i++)
            {
                if (Busy[start + i])
                {
                    start += i;
                    break;
                }
            }
            if (!Busy[start]) return start;
        }
    }
}

public class Disk
{
    public int ID;
    public int Speed;
    public int Capacity;
    public int InitialCapacity;

    public override string ToString() => $"{ID} {Speed} {Capacity}";
}