Codeforces Marathon veeroute 2019

Solver.cs

// #undef DEBUG

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

namespace Solver
{
	class MainClass
	{
		const int SUMMON_COST = 240;
		const int MAX_TIME = 14000;
		static Random random = new Random ();

		public static void Main (string[] args)
		{
			Board board = new Board ();
			Solution solution = new Solution (board);

			string result = solution.Solve ();
			#if !DEBUG
			Console.Write (result);
			#endif
		}

		class Solution
		{
			public Board Board;
			public List<Worker> Workers;

			public Solution (Board board)
			{
				this.Board = board;
			}

			public string Solve ()
			{
				Stopwatch sw = Stopwatch.StartNew ();
				JobPackage.Base = Board.Base;
				Worker.Base = Board.Base;

				List<JobPackage> packages = Board.Jobs.Select (j => new JobPackage (new Job (j))).ToList ();
				List<JobPackage> pack4plus = packages.Where (p => p.Workers >= 4).ToList ();
				pack4plus = MergePackages (pack4plus, 2);
				List<Job> job4plus = pack4plus.SelectMany (p => p.Jobs).ToList ();
				foreach (JobPackage p in pack4plus) {
					p.Workers -= 4;
					foreach (Job j in p.Jobs)
						j.Workers -= 4;
				}
				packages = packages.Where (p => p.Workers < 4).Union (pack4plus.Where (p => p.Workers > 0)).ToList ();
				packages = MergePackages (packages, 20);
				job4plus.ForEach (j => j.Workers += 4);
				packages.AddRange (pack4plus.Where (p => p.Workers == 0));
				pack4plus.ForEach (p => p.Workers = 4);
				packages = packages.OrderByDescending (p => p.Workers).ToList ();

				packages = packages.Where (p => p.Jobs.Count > 0).ToList ();
				packages.ForEach (p => p.Compress ());

				Workers = packages.SelectMany (p => p.CreateWorkers (true)).ToList ();
				List<Job> jobs = Workers.SelectMany (w => w.Jobs).Distinct ().ToList ();


				#if DEBUG
				foreach (Job j in jobs) {
					if (j.Workers > Workers.Count (w => w.Jobs.Contains (j)))
						Console.WriteLine ("too few workers for job " + j.ID);
					if (j.Workers < Workers.Count (w => w.Jobs.Contains (j)))
						Console.WriteLine ("too many workers for job " + j.ID);
					if (Board.Jobs.Find (j2 => j2.ID == j.ID).Workers != j.Workers)
						Console.WriteLine ("modified input for job " + j.ID);
					if (j.ChosenStart < j.FirstStart || j.ChosenStart > j.LastStart)
						Console.WriteLine ("invalid start time for job " + j.ID);
				}
				foreach (Worker w in Workers) {
					if (w.Jobs.Count == 0)
						continue;
					int t = w.Jobs [0].ChosenStart + w.Jobs [0].Duration;
					for (int i = 1; i < w.Jobs.Count; i++) {
						t += w.Jobs [i - 1].Dist (w.Jobs [i]);
						if (t > w.Jobs [i].ChosenStart)
							Console.WriteLine ("colliding start for job " + w.Jobs [i].ID);
						t = w.Jobs [i].ChosenStart;
					}
				}
				#endif
				CombineWorkers ();
				int oldScore = 0;
				int bestScore = 0;
				int oldWorkers = 0;
				string result = "";
				while (sw.ElapsedMilliseconds < MAX_TIME) {
					int score = jobs.Sum (j => j.Value) - Workers.Sum (w => w.Cost ());
					Console.Error.WriteLine ("score: " + score + " @" + sw.ElapsedMilliseconds + "  w:" + Workers.Count);
					if (score > bestScore) {
						bestScore = score;
						result = this.ToString ();
					}
					ShiftBlockingJobs ();
					ShiftJobs ();
					bool moveJob = false;
					if (score - oldScore < 100 && Workers.Count == oldWorkers) {
						moveJob = true;
						ChangeJobTime (jobs);
					}
					oldScore = score;
					oldWorkers = Workers.Count;
					CombineWorkers ();
					CompressWorkers ();
					CleanupJobs (moveJob);
				}
				CombineWorkers ();
				CompressWorkers ();
				ShiftJobs ();
				CompressWorkers ();

				if (jobs.Sum (j => j.Value) - Workers.Sum (w => w.Cost ()) > bestScore)
					result = this.ToString ();

				//int[] histo = new int[800];
				//foreach(Job j in jobs)
				//{
				//    for (int t = j.FirstStart; t < j.LastStart; t++)
				//    {
				//        histo[t]++;
				//    }
				//}
				//for (int t = 0; t < histo.Length; t++)
				//{
				//    if (histo[t] > 0) Console.Write(t + ": " + histo[t] + "\t");
				//}
				//Console.Error.WriteLine(string.Join("\n",
				//    Workers.Select(w => new
				//    {
				//        t = w.TotalTime(),
				//        start = w.Jobs[0].ChosenStart,
				//        end = w.Jobs.Last().ChosenStart + w.Jobs.Last().Duration,
				//        jobs = w.Jobs.Count,
				//        worker = w
				//    }).OrderBy(x => x.jobs).Select(x => $"t:{x.t}    start:{x.start}    end:{x.end}    jobs:{x.jobs}    {string.Join(" ", x.worker.Jobs.Select(j => j.ID))}")));
				Console.Error.WriteLine ("");
				Console.Error.WriteLine ("swaps: " + swap + "/" + swapTries);
				Console.Error.WriteLine ("workers: " + Workers.Count);
				Console.Error.WriteLine ("jobs: " + jobs.Count + "/" + Board.Jobs.Count);
				Console.Error.WriteLine ("total time: " + Workers.Sum (w => w.TotalTime ()));
				Console.Error.WriteLine ("travel time: " + Workers.Sum (w => w.TravelTime ()));
				Console.Error.WriteLine ("working time: " + Workers.Sum (w => w.WorkingTime ()));
				Console.Error.WriteLine ("idle time: " + Workers.Sum (w => w.IdleTime ()));
				Console.Error.WriteLine ("score: " + (jobs.Sum (j => j.Value) - Workers.Sum (w => w.Cost ())) + " @" + sw.ElapsedMilliseconds);
				return result;
			}

			private void ChangeJobTime (List<Job> jobs)
			{
				for (int i = 0; i < 100; i++) {
					Job j = jobs [random.Next (jobs.Count)];
					int initialTime = j.ChosenStart;
					bool shifted = false;
					for (int k = 0; k < 10; k++) {
						j.ChosenStart = random.Next (j.FirstStart, j.LastStart + 1);
						List<Worker> candidates = new List<Worker> ();
						foreach (Worker w in Workers) {
							if (w.Jobs.Count == 0 || j.ChosenStart < w.Jobs [0].ChosenStart || j.ChosenStart > w.Jobs [w.Jobs.Count - 1].ChosenStart)
								continue;
							if (w.Cost (j) == 0) {
								candidates.Add (w);
								if (candidates.Count == j.Workers)
									break;
							}
						}

						if (candidates.Count == j.Workers) {
							shifted = true;
							foreach (Worker w in Workers) {
								if (w.Jobs.Contains (j))
									w.Jobs.Remove (j);
							}
							foreach (Worker w in candidates)
								w.AddAction (j);
							break;
						}
					}
					if (!shifted)
						j.ChosenStart = initialTime;
				}
			}

			private void ShiftBlockingJobs ()
			{
				int minJobs = Workers.Min (w => w.Jobs.Count);
				foreach (Worker worker in Workers) {
					if (worker.Jobs.Count != minJobs)
						continue;
					List<Job> toRemove = worker.Jobs.ToList ();
					List<Worker>[] substitutes = new List<Worker>[toRemove.Count];
					int[] newTimes = new int[toRemove.Count];
					bool[] zero = new bool[toRemove.Count];
					HashSet<Worker> allSubstitutes = new HashSet<Worker> ();
					for (int jobIndex = 0; jobIndex < toRemove.Count; jobIndex++) {
						Job j = toRemove [jobIndex];
						int oldStart = j.ChosenStart;
						for (int newStart = j.FirstStart; newStart <= j.LastStart; newStart++) {
							List<Worker> candidates = new List<Worker> ();
							List<Worker> zeroCost = new List<Worker> ();
							j.ChosenStart = newStart;
							foreach (Worker w in Workers) {
								if (allSubstitutes.Contains (w))
									continue;
								int cost = w.Cost (j);
								if (cost == 0)
									zeroCost.Add (w);
								if (cost < SUMMON_COST)
									candidates.Add (w);
							}
							if (zeroCost.Count >= j.Workers) {
								candidates = zeroCost;
								zero [jobIndex] = true;
							}
							if (candidates.Count >= j.Workers) {
								candidates = candidates.Take (j.Workers).ToList ();
								substitutes [jobIndex] = candidates;
								newTimes [jobIndex] = newStart;
								candidates.ForEach (c => allSubstitutes.Add (c));
								break;
							}
						}
						j.ChosenStart = oldStart;
					}

					bool replace = !substitutes.Any (s => s == null);
					for (int jobIndex = 0; jobIndex < toRemove.Count; jobIndex++) {
						if (!replace && !zero [jobIndex])
							continue;
						Job j = toRemove [jobIndex];
						foreach (Worker w in Workers) {
							if (w.Jobs.Contains (j))
								w.Jobs.Remove (j);
						}
						j.ChosenStart = newTimes [jobIndex];
						foreach (Worker w in substitutes[jobIndex])
							w.AddAction (j);
					}
				}
				Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
			}

			private void CombineWorkers ()
			{
				List<WorkerPair> pairs = new List<WorkerPair> ();
				foreach (Worker w1 in Workers) {
					foreach (Worker w2 in Workers) {
						if (w1.CanMerge (w2))
							pairs.Add (new WorkerPair (w1.Diff (w2), w1, w2));
					}
				}
				pairs = pairs.OrderBy (p => p.Diff).ToList ();
				foreach (WorkerPair p in pairs)
					p.Merge ();

				Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
			}

			private void ShiftJobs ()
			{
				Job[] jobs = new Job[Board.Jobs.Count + 2];
				List<Worker>[] terminalWorkers = new List<Worker>[jobs.Length];
				List<Worker>[] workersByJob = new List<Worker>[jobs.Length];
				for (int i = 0; i < workersByJob.Length; i++) {
					workersByJob [i] = new List<Worker> ();
					terminalWorkers [i] = new List<Worker> ();
				}
				foreach (Worker w in Workers) {
					foreach (Job job in w.Jobs) {
						workersByJob [job.ID].Add (w);
						jobs [job.ID] = job;
					}
					Job j = w.Jobs [w.Jobs.Count - 1];
					terminalWorkers [j.ID].Add (w);
				}

				for (int i = 0; i < 1000; i++) {
					int index = random.Next (2, jobs.Length);
					if (terminalWorkers [index].Count == 0)
						continue;
					Job current = jobs [index];

					List<Job> candidates = new List<Job> ();
					foreach (Job j in jobs) {
						if (j == null || j.Workers > terminalWorkers [index].Count || j == current)
							continue;
						if (current.ChosenStart + current.Duration + current.Dist (j) > j.LastStart)
							continue;
						candidates.Add (j);
					}

					while (candidates.Count > 0) {
						Job after = candidates [random.Next (candidates.Count - 1)];
						candidates.Remove (after);
						int oldCost = 0;
						foreach (Worker w in workersByJob[after.ID])
							oldCost += w.CostSavingWithout (after);

						int willStart = current.ChosenStart + current.Duration + current.Dist (after);
						if (willStart < after.FirstStart)
							willStart = after.FirstStart;
						int willEnd = willStart + after.Duration + after.Dist (Board.Base);
						int oldEnd = current.ChosenStart + current.Duration + current.Dist (Board.Base);
						int newCost = current.Workers * (willEnd - oldEnd);

						if (newCost <= oldCost) {
							foreach (Worker w in workersByJob[after.ID]) {
								if (w.Jobs.Count > 1 && w.Jobs [w.Jobs.Count - 1] == after)
									terminalWorkers [w.Jobs [w.Jobs.Count - 2].ID].Add (w);
								w.Jobs.Remove (after);
							}
							terminalWorkers [after.ID].Clear ();
							workersByJob [after.ID].Clear ();
							after.ChosenStart = willStart;
							for (int j = 0; j < after.Workers; j++) {
								Worker w = terminalWorkers [current.ID] [0];
								terminalWorkers [current.ID].RemoveAt (0);
								w.AddAction (after);
								terminalWorkers [after.ID].Add (w);
								workersByJob [after.ID].Add (w);
							}
							break;
						}
					}
				}

				for (int i = 0; i < workersByJob.Length; i++) {
					terminalWorkers [i] = new List<Worker> ();
				}
				foreach (Worker w in Workers) {
					if (w.Jobs.Count == 0)
						continue;
					Job j = w.Jobs [0];
					terminalWorkers [j.ID].Add (w);
				}

				for (int i = 0; i < 1000; i++) {
					int index = random.Next (2, jobs.Length);
					if (terminalWorkers [index].Count == 0)
						continue;
					Job current = jobs [index];

					List<Job> candidates = new List<Job> ();
					foreach (Job j in jobs) {
						if (j == null || j.Workers > terminalWorkers [index].Count || j == current)
							continue;
						if (current.ChosenStart - j.Duration - current.Dist (j) < j.FirstStart)
							continue;
						candidates.Add (j);
					}

					while (candidates.Count > 0) {
						Job before = candidates [random.Next (candidates.Count - 1)];
						candidates.Remove (before);
						int oldCost = 0;
						foreach (Worker w in workersByJob[before.ID])
							oldCost += w.CostSavingWithout (before);

						int willStart = current.ChosenStart - before.Duration - current.Dist (before);
						if (willStart > before.LastStart)
							willStart = before.LastStart;
						int willEnd = willStart - before.Dist (Board.Base);
						int oldEnd = current.ChosenStart - current.Dist (Board.Base);
						int newCost = current.Workers * (oldEnd - willEnd);

						if (newCost <= oldCost) {
							foreach (Worker w in workersByJob[before.ID]) {
								if (w.Jobs.Count > 1 && w.Jobs [0] == before)
									terminalWorkers [w.Jobs [1].ID].Add (w);
								w.Jobs.Remove (before);
							}
							terminalWorkers [before.ID].Clear ();
							workersByJob [before.ID].Clear ();
							before.ChosenStart = willStart;
							for (int j = 0; j < before.Workers; j++) {
								Worker w = terminalWorkers [current.ID] [0];
								terminalWorkers [current.ID].RemoveAt (0);
								w.AddAction (before);
								terminalWorkers [before.ID].Add (w);
								workersByJob [before.ID].Add (w);
							}
							break;
						}
					}
				}

				Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
			}

			private List<JobPackage> MergePackages (List<JobPackage> packages, int workerDiff)
			{
				for (int dist = 1; dist <= 200; dist++) {
					bool merged = true;
					while (merged) {
						merged = false;
						foreach (JobPackage p1 in packages) {
							foreach (JobPackage p2 in packages) {
								if (p1.Add (p2, dist, workerDiff)) {
									merged = true;
									break;
								}
							}
						}
						packages = packages.Where (p => p.Jobs.Count > 0).ToList ();
					}
				}
				return packages;
			}

			private void CompressWorkers ()
			{
				List<Job> jobs = Workers.SelectMany (w => w.Jobs).Distinct ().ToList ();
				List<Worker>[] workersByJob = new List<Worker>[jobs.Max (j => j.ID) + 1];
				for (int i = 1; i < workersByJob.Length; i++)
					workersByJob [i] = new List<Worker> ();
				foreach (Worker w in Workers) {
					foreach (Job j in w.Jobs)
						workersByJob [j.ID].Add (w);
				}
				List<Job> waiting = jobs.Where (j => !workersByJob [j.ID].Any (w => j == w.Jobs.Last ())).ToList ();

				bool changed = true;
				while (changed) {
					changed = false;
					foreach (Job j in waiting) {
						int minDelay = j.LastStart - j.ChosenStart;
						foreach (Worker w in workersByJob[j.ID]) {
							Job next = w.Jobs.FirstOrDefault (n => n.ChosenStart > j.ChosenStart);
							if (next == null)
								continue;
							minDelay = Math.Min (minDelay, next.ChosenStart - j.ChosenStart - j.Duration - j.Dist (next));
						}
						j.ChosenStart += minDelay;
						if (minDelay > 0)
							changed = true;
					}
				}

				waiting = jobs.Where (j => !workersByJob [j.ID].Any (w => j == w.Jobs [0])).ToList ();

				changed = true;
				while (changed) {
					changed = false;
					foreach (Job j in waiting) {
						int minDelay = j.ChosenStart - j.FirstStart;
						foreach (Worker w in workersByJob[j.ID]) {
							Job prev = w.Jobs.LastOrDefault (n => n.ChosenStart < j.ChosenStart);
							if (prev == null)
								continue;
							minDelay = Math.Min (minDelay, j.ChosenStart - prev.ChosenStart - prev.Duration - j.Dist (prev));
						}
						j.ChosenStart -= minDelay;
						if (minDelay > 0)
							changed = true;
					}
				}
			}

			static long swap = 0;
			static long swapTries = 0;

			public void CleanupJobs (bool moveJob)
			{
				// move first or last job to another worker
				bool[] noMatch = new bool[2010];
				foreach (Worker w1 in Workers) {
					if (w1.Jobs.Count == 0)
						continue;

					List<Job> jobs = new List<Job> { w1.Jobs [0] };
					if (w1.Jobs.Count > 1)
						jobs.Add (w1.Jobs [w1.Jobs.Count - 1]);
					foreach (Job job in jobs) {
						if (noMatch [job.ID])
							continue;
						noMatch [job.ID] = true;
						int costSavingWithout = w1.CostSavingWithout (job);
						List<Worker> candidates = new List<Worker> ();
						foreach (Worker w2 in Workers) {
							if (w2.Jobs.Count == 0)
								continue;
							int cost = w2.Cost (job);
							if (cost == costSavingWithout)
								candidates.Add (w2);
							if (cost < costSavingWithout) {
								candidates.Clear ();
								w2.AddAction (job);
								w1.Jobs.Remove (job);
								noMatch [job.ID] = false;
								break;
							}
						}

						if (candidates.Count > 0) {
							Worker w2 = candidates [random.Next (candidates.Count)];
							w2.AddAction (job);
							w1.Jobs.Remove (job);
						}
					}

					// swap 1 vs 0
					if (moveJob) {
						for (int i = 0; i < 3000; i++) {
							//swapTries++;
							if (w1.Jobs.Count == 0)
								break;
							Worker w2 = Workers [random.Next (Workers.Count)];
							if (w2.Jobs.Count == 0 || w2.Jobs.Count < w1.Jobs.Count + 1 || w1 == w2)
								continue;
							// random swap
							Job job = w1.Jobs [random.Next (w1.Jobs.Count)];
							if (w2.Cost (job) == 0) {
								w2.AddAction (job);
								w1.Jobs.Remove (job);
								//swap++;
							}
						}
					}
				}

				List<JobConnection> connections = new List<JobConnection> ();
				foreach (Worker w in Workers) {
					for (int i = 1; i < w.Jobs.Count; i++) {
						int dist = w.Jobs [i - 1].Dist (w.Jobs [i]);
						if (dist > 1)
							connections.Add (new JobConnection (w, i, dist));
					}
				}
				int take = Math.Max (Math.Min (connections.Count, 1000), connections.Count / 5);
				//if (moveJob) take = connections.Count;
				connections = connections.OrderByDescending (c => c.Dist).Take (take).ToList ();
				connections = connections.OrderByDescending (c => c.Worker.Jobs [c.JobIndex].ChosenStart).ToList ();

				// crossover
				foreach (JobConnection c in connections) {
					Worker w1 = c.Worker;
					Job j1 = w1.Jobs [c.JobIndex];
					for (int i = 0; i < 100; i++) {
						swapTries++;
						Worker w2 = Workers [random.Next (Workers.Count)];
						if (w2.Jobs.Count == 0 || w1 == w2)
							continue;

						int j2Index = 0;
						while (j2Index < w2.Jobs.Count && w2.Jobs [j2Index].ChosenStart < j1.ChosenStart)
							j2Index++;
						if (j2Index == w2.Jobs.Count)
							continue;
						Job j2 = w2.Jobs [j2Index];
						// if (w1.Jobs[c.JobIndex - 1].Dist(j2) > c.Dist) continue;

						int idx1 = w1.Jobs.IndexOf (j1);
						int idx2 = w2.Jobs.IndexOf (j2);
						if (idx1 == 0 && idx2 == 0)
							continue; // no crossover
						if (idx1 > 0 && w1.Jobs [idx1 - 1].ChosenStart + w1.Jobs [idx1 - 1].Duration + w1.Jobs [idx1 - 1].Dist (j2) > j2.ChosenStart)
							continue; // time colliding
						if (idx2 > 0 && w2.Jobs [idx2 - 1].ChosenStart + w2.Jobs [idx2 - 1].Duration + w2.Jobs [idx2 - 1].Dist (j1) > j1.ChosenStart)
							continue;
						if (idx1 > 0 && idx2 > 0 && w1.Jobs [idx1 - 1].Dist (j2) >= w1.Jobs [idx1 - 1].Dist (j1) && w2.Jobs [idx2 - 1].Dist (j1) >= w2.Jobs [idx2 - 1].Dist (j2))
							continue; // no improvement


						Worker w1_ = new Worker ();
						Worker w2_ = new Worker ();
						for (int k = 0; k < idx1; k++)
							w1_.Jobs.Add (w1.Jobs [k]);
						for (int k = 0; k < idx2; k++)
							w2_.Jobs.Add (w2.Jobs [k]);
						for (int k = idx1; k < w1.Jobs.Count; k++)
							w2_.Jobs.Add (w1.Jobs [k]);
						for (int k = idx2; k < w2.Jobs.Count; k++)
							w1_.Jobs.Add (w2.Jobs [k]);

						if (w1_.Cost () + w2_.Cost () <= w1.Cost () + w2.Cost ()) {
							w1.Jobs = w1_.Jobs;
							w2.Jobs = w2_.Jobs;
							swap++;
							break;
						}
					}
				}

				Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
			}

			public override string ToString ()
			{
				StringBuilder result = new StringBuilder ();
				foreach (Worker w in Workers)
					result.AppendLine (w.ToString ());
				return result.ToString ();
			}
		}

		class JobConnection
		{
			public Worker Worker;
			public int JobIndex;
			public int Dist;

			public JobConnection (Worker worker, int jobIndex, int dist)
			{
				this.Worker = worker;
				this.JobIndex = jobIndex;
				this.Dist = dist;
			}
		}

		class WorkerPair
		{
			public int Diff;
			public Worker Worker1;
			public Worker Worker2;

			public WorkerPair (int diff, Worker w1, Worker w2)
			{
				this.Diff = diff;
				this.Worker1 = w1;
				this.Worker2 = w2;
			}

			public void Merge ()
			{
				Worker1.Merge (Worker2);
			}
		}

		class Board
		{
			public Job Base;
			public List<Job> Jobs = new List<Job> ();

			public Board ()
			{
				int n = int.Parse (Console.ReadLine ());
				int[] nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
				Base = new Job (nums [0], nums [1], 1, 0, 0, 0, 0);
				for (int i = 2; i <= n; i++) {
					nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
					Jobs.Add (new Job (nums [0], nums [1], i, nums [2], nums [3], nums [4], nums [5]));
				}
				Jobs = Jobs.OrderBy (j => j.FirstStart).ToList ();
			}
		}

		class Job
		{
			public int X, Y, ID;
			public int Duration, FirstStart, LastStart, Workers;
			public int Value;
			public int Created;
			public int ChosenStart;

			public Job (int x, int y, int id, int duration, int workers, int firstStart, int lastEnd)
			{
				this.ID = id;
				this.X = x;
				this.Y = y;
				this.Duration = duration;
				this.Workers = workers;
				this.FirstStart = firstStart;
				this.LastStart = lastEnd - duration;
				Value = duration * workers * (workers + 5);
			}

			public Job (Job j) : this (j.X, j.Y, j.ID, j.Duration, j.Workers, j.FirstStart, j.LastStart + j.Duration)
			{
				this.ChosenStart = j.ChosenStart;
			}

			public int Dist (Job job)
			{
				return Math.Abs (X - job.X) + Math.Abs (Y - job.Y);
			}

			public override string ToString ()
			{
				return ID + " @" + ChosenStart;
			}
		}

		class Worker : IComparable<Worker>
		{
			public List<Job> Jobs = new List<Job> ();
			public static Job Base;

			public int ExtraCost;
			public int ExtraDist;
			public int PseudoCost;

			public void AddAction (Job job)
			{
				int index = 0;
				while (index < Jobs.Count && Jobs [index].ChosenStart < job.ChosenStart)
					index++;
				Jobs.Insert (index, job);
			}

			public int TotalTime ()
			{
				int start = Jobs [0].ChosenStart - Base.Dist (Jobs [0]);
				int end = Jobs.Last ().ChosenStart + Jobs.Last ().Duration + Base.Dist (Jobs.Last ());
				return end - start;
			}

			public int WorkingTime ()
			{
				return Jobs.Sum (j => j.Duration);
			}

			public int TravelTime ()
			{
				int result = Base.Dist (Jobs [0]) + Base.Dist (Jobs.Last ());
				for (int i = 0; i < Jobs.Count - 1; i++) {
					result += Jobs [i].Dist (Jobs [i + 1]);
				}
				return result;
			}

			public int IdleTime ()
			{
				return TotalTime () - TravelTime () - WorkingTime ();
			}

			public int Cost ()
			{
				if (Jobs.Count == 0)
					return 0;
				Job last = Jobs [Jobs.Count - 1];
				return SUMMON_COST + (last.ChosenStart + last.Duration - Jobs [0].ChosenStart) + last.Dist (Base) + Jobs [0].Dist (Base);
			}

			public int Cost (Job job)
			{
				ExtraCost = 0;
				PseudoCost = ExtraCost;

				if (Jobs.Count == 0) {
					ExtraCost = 2 * job.Dist (Base) + SUMMON_COST;
					return ExtraCost;
				}

				Job prev = null, next = null;
				if (job.ChosenStart <= Jobs [0].ChosenStart)
					next = Jobs [0];
				else if (job.ChosenStart >= Jobs [Jobs.Count - 1].ChosenStart)
					prev = Jobs [Jobs.Count - 1];
				else {
					int left = 0, right = Jobs.Count - 1;
					while (left + 1 < right) {
						int middle = (left + right) / 2;
						if (Jobs [middle].ChosenStart < job.ChosenStart)
							left = middle;
						else
							right = middle;
					}
					int index = left;
					while (Jobs [index + 1].ChosenStart < job.ChosenStart)
						index++;
					prev = Jobs [index];
					if (prev.ChosenStart < job.ChosenStart)
						index++;
					next = Jobs [index];
				}

				if (prev != null && prev.ChosenStart + prev.Duration + prev.Dist (job) > job.ChosenStart ||
				    next != null && job.ChosenStart + job.Duration + job.Dist (next) > next.ChosenStart) {
					ExtraCost = int.MaxValue;
					PseudoCost = ExtraCost;
					return ExtraCost;
				}

				if (prev != null && next != null) { // in the middle
					ExtraDist = job.Dist (next) + job.Dist (prev) - prev.Dist (next); // TODO: bonus for small gap on one end
					return ExtraCost;
				}
				if (prev != null) { // last in chain
					int initial = prev.ChosenStart + prev.Duration + prev.Dist (Base);
					int final = job.ChosenStart + job.Duration + job.Dist (Base);
					ExtraDist = job.Dist (prev) + job.Dist (Base) - prev.Dist (Base);
					ExtraCost = final - initial;
					PseudoCost = job.ChosenStart - prev.ChosenStart - prev.Duration;
				}
				if (next != null) { // first in chain
					int initial = next.ChosenStart - next.Dist (Base);
					int final = job.ChosenStart - job.Dist (Base);
					ExtraDist = job.Dist (next) + job.Dist (Base) - next.Dist (Base);
					ExtraCost = initial - final;
					PseudoCost = next.FirstStart - job.ChosenStart - job.Duration;
				}
				return ExtraCost;
			}

			public int CostSavingWithout (Job job)
			{
				if (Jobs.Count == 1)
					return SUMMON_COST + 2 * Base.Dist (job);

				if (job == Jobs [0]) {
					int initial = Jobs [0].ChosenStart - Base.Dist (Jobs [0]);
					int final = Jobs [1].ChosenStart - Base.Dist (Jobs [1]);
					return final - initial;
				}

				if (job == Jobs [Jobs.Count - 1]) {
					int initial = job.ChosenStart + job.Duration + Base.Dist (job);
					int final = Jobs [Jobs.Count - 2].ChosenStart + Jobs [Jobs.Count - 2].Duration + Base.Dist (Jobs [Jobs.Count - 2]);
					return initial - final;
				}

				return 0;
			}

			public override string ToString ()
			{
				StringBuilder result = new StringBuilder ();
				result.AppendLine ("start " + (Jobs [0].ChosenStart - Base.Dist (Jobs [0])) + " " + Base.ID);
				Job prev = Base;
				int time = Jobs [0].ChosenStart - Base.Dist (Jobs [0]);
				foreach (Job action in Jobs) {
					result.AppendLine ("arrive " + (time + prev.Dist (action)) + " " + action.ID);
					result.AppendLine ("work " + action.ChosenStart + " " + (action.ChosenStart + action.Duration) + " " + action.ID);
					time = action.ChosenStart + action.Duration;
					prev = action;
				}
				result.AppendLine ("arrive " + (Jobs.Last ().ChosenStart + Jobs.Last ().Duration + Jobs.Last ().Dist (Base)) + " " + Base.ID);
				result.Append ("end");
				return result.ToString ();
			}

			public int Diff (Worker w)
			{
				Job last = this.Jobs.Last ();
				return w.Jobs [0].ChosenStart - (last.ChosenStart + last.Duration);
			}

			public bool CanMerge (Worker w)
			{
				if (this.Jobs.Count == 0 || w.Jobs.Count == 0)
					return false;
				Job last = this.Jobs.Last ();
				return last.ChosenStart + last.Duration + last.Dist (w.Jobs [0]) <= w.Jobs [0].ChosenStart;
			}

			public void Merge (Worker w)
			{
				if (!CanMerge (w))
					return;
				this.Jobs.AddRange (w.Jobs);
				w.Jobs.Clear ();
			}

			public int WorkerDiff ()
			{
				int result = 0;
				for (int i = 1; i < Jobs.Count; i++)
					result += Math.Abs (Jobs [i - 1].Workers - Jobs [i].Workers);
				return result;
			}

			public int CompareTo (Worker other)
			{
				for (int i = 0; i < Jobs.Count; i++) {
					if (i == other.Jobs.Count)
						return -1;
					if (this.Jobs [i] != other.Jobs [i])
						return this.Jobs [i].ID.CompareTo (other.Jobs [i].ID);
				}
				if (this.Jobs.Count < other.Jobs.Count)
					return 1;
				return 0;
			}
		}

		class JobPackage
		{
			public int FirstStart;
			public int LastStart;
			public int Duration;
			public List<Job> Jobs = new List<Job> ();

			public Job StartLocation { get { return Jobs [0]; } }

			public Job EndLocation { get { return Jobs [Jobs.Count - 1]; } }

			public int Workers;
			public static Job Base;

			public JobPackage (Job job)
			{
				Jobs.Add (job);
				FirstStart = job.FirstStart;
				LastStart = job.LastStart;
				Duration = job.Duration;
				Workers = job.Workers;
			}

			public JobPackage (JobPackage backup)
			{
				this.Jobs = backup.Jobs.ToList ();
				this.FirstStart = backup.FirstStart;
				this.LastStart = backup.LastStart;
				this.Duration = backup.Duration;
				this.Workers = backup.Workers;
			}

			public bool Add (JobPackage package, int maxDist, int workerDiff)
			{
				if (this == package || this.Jobs.Count == 0 || package.Jobs.Count == 0)
					return false;
				int dist = this.Dist (package);
				int penalty = workerDiff * Math.Abs (this.Jobs [Jobs.Count - 1].Workers - package.Jobs [0].Workers);
				if (dist + penalty > maxDist)
					return false;

				int firstEnd = Math.Max (FirstStart + Duration + dist, package.FirstStart);
				int lastEnd = Math.Min (LastStart + Duration + dist, package.LastStart);
				int idleTime = package.FirstStart - (LastStart + Duration + dist);
				if (lastEnd < firstEnd && idleTime < 0)
					return false;

				//JobPackage backup = new JobPackage (this);
				if (idleTime > 0) {
					int flexibility = Math.Max (LastStart - FirstStart, package.LastStart - package.FirstStart) * 3 / (this.Jobs.Count + package.Jobs.Count);
					if (dist + penalty + idleTime + flexibility > maxDist)
						return false;
					FirstStart = LastStart;
					Duration += dist + package.Duration + idleTime;
					Jobs.AddRange (package.Jobs);
					package.Jobs.Clear ();
					//if (!Validate ())
					//	backup.Add (package, maxDist);
					return true;
				}

				if (Math.Max (FirstStart, firstEnd - Duration - dist) > Math.Min (LastStart, lastEnd - Duration - dist))
					return false;
				FirstStart = Math.Max (FirstStart, firstEnd - Duration - dist);
				LastStart = Math.Min (LastStart, lastEnd - Duration - dist);
				Duration += dist + package.Duration;
				Jobs.AddRange (package.Jobs);
				package.Jobs.Clear ();
				//if (!Validate ())
				//	backup.Add (package, maxDist);
				return true;
			}

			public bool Validate ()
			{
				int t = FirstStart;
				for (int i = 0; i < Jobs.Count; i++) {
					Job j = Jobs [i];
					if (t < j.FirstStart)
						t = j.FirstStart;
					if (t > j.LastStart)
						return false;
					t += j.Duration;
					if (i < Jobs.Count - 1)
						t += j.Dist (Jobs [i + 1]);
				}
				return true;
			}

			public void Compress ()
			{
				Worker w = CreateWorkers (false).First ();
				int time = w.TotalTime ();
				int workerDiff = w.WorkerDiff ();
				for (int swapIndex = 0; swapIndex < Jobs.Count - 2; swapIndex++) {
					for (int type = 0; type < 6; type++) {
						List<JobPackage> packages = Jobs.Select (j => new JobPackage (new Job (j))).ToList ();
						List<JobPackage> old = packages.ToList ();
						int i1 = new int[] { 0, 0, 1, 1, 2, 2 } [0];
						int i2 = new int[] { 1, 2, 0, 2, 0, 1 } [0];
						int i3 = new int[] { 2, 1, 2, 0, 1, 0 } [0];
						packages [swapIndex] = old [swapIndex + i1];
						packages [swapIndex + 1] = old [swapIndex + i2];
						packages [swapIndex + 2] = old [swapIndex + i3];

						bool valid = true;
						for (int i = 1; i < packages.Count; i++) {
							if (!packages [0].Add (packages [i], 10000, 0))
								valid = false;
						}
						if (!valid)
							continue;
						Worker w2 = packages [0].CreateWorkers (false).First ();
						if (w2.TotalTime () < time || w2.TotalTime () == time && w2.WorkerDiff () < workerDiff) {
							time = w2.TotalTime ();
							workerDiff = w2.WorkerDiff ();
							this.FirstStart = packages [0].FirstStart;
							this.LastStart = packages [0].LastStart;
							this.Duration = packages [0].Duration;
							this.Jobs = packages [0].Jobs;
						}
					}
				}
			}

			public IEnumerable<Worker> CreateWorkers (bool count)
			{
				int t = FirstStart;
				for (int i = 0; i < Jobs.Count; i++) {
					Job j = Jobs [i];
					if (t < j.FirstStart)
						t = j.FirstStart;
					j.ChosenStart = t;
					t += j.Duration;
					if (i < Jobs.Count - 1)
						t += j.Dist (Jobs [i + 1]);
				}

				for (int i = 0; i < 7; i++) {
					Worker w = new Worker ();
					foreach (Job j in Jobs) {
						if (count) {
							if (j.Created < j.Workers) {
								w.Jobs.Add (j);
								j.Created++;
							}
						} else if (i < j.Workers)
							w.Jobs.Add (j);
					}
					yield return w;
				}
			}

			public int Dist (JobPackage other)
			{
				return this.EndLocation.Dist (other.StartLocation);
			}
		}
	}
}