using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input5"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4 6"); WillReturn.Add("5 5"); WillReturn.Add("2 3"); WillReturn.Add("4 4"); WillReturn.Add("1 1"); //YES //問題文中の良い壁の例と同じ。 //どのブロックも180度回転させずに積めば良い壁になる。 //0番目のブロックを180度回転させても良い壁には変わりない。 } else if (InputPattern == "Input2") { WillReturn.Add("4 6"); WillReturn.Add("3 5"); WillReturn.Add("3 4"); WillReturn.Add("4 4"); WillReturn.Add("1 2"); //NO //問題文中の悪い壁の例と同じ。 //180度回転をどのように使っても良い壁はできない。 } else if (InputPattern == "Input3") { WillReturn.Add("2 4"); WillReturn.Add("0 1"); WillReturn.Add("0 1"); //YES //どちらかのブロックを180度回転させて積めば良い壁になる } else if (InputPattern == "Input4") { WillReturn.Add("5 10"); WillReturn.Add("8 8"); WillReturn.Add("0 0"); WillReturn.Add("2 4"); WillReturn.Add("2 3"); WillReturn.Add("8 8"); //YES //良い壁にできます } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct BlookDef { internal int L; internal int R; internal int KaitenL; internal int KaitenR; } static int M; static void Main() { List InputList = GetInputList(); int[] wkArr = { }; Action SplitAct = (pStr) => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); SplitAct(InputList[0]); M = wkArr[1]; var BlookList = new List(); for (int I = 1; I <= InputList.Count - 1; I++) { SplitAct(InputList[I]); BlookList.Add(CreateBlockInfo(wkArr[0], wkArr[1])); } BlookList.Sort((A, B) => A.L.CompareTo(B.L)); Console.WriteLine(CanCreateGoodWall(BlookList) ? "YES" : "NO"); } //ブロック情報を作成 static BlookDef CreateBlockInfo(int pL, int pR) { BlookDef WillReturn; int NewL = M - 1 - pR; int NewR = M - 1 - pL; //L < KaitenL とする if (pL < NewL) { WillReturn.L = pL; WillReturn.R = pR; WillReturn.KaitenL = NewL; WillReturn.KaitenR = NewR; } else { WillReturn.L = NewL; WillReturn.R = NewR; WillReturn.KaitenL = pL; WillReturn.KaitenR = pR; } return WillReturn; } //良い壁を作成できるかを返す static bool CanCreateGoodWall(List pBlookList) { //var IsPinkArr = new System.Collections.BitArray(M); var IsPinkArr = new bool[M]; foreach (BlookDef EachBlock in pBlookList) { //左に詰めて置けるなら、置く bool CanSetLeft = true; for (int I = EachBlock.L; I <= EachBlock.R; I++) { if (IsPinkArr[I]) { CanSetLeft = false; break; } } if (CanSetLeft) { for (int I = EachBlock.L; I <= EachBlock.R; I++) { IsPinkArr[I] = true; } continue; } //左に詰めて置けないなら、180度回転させて、右に置く bool CanSetRight = true; for (int I = EachBlock.KaitenL; I <= EachBlock.KaitenR; I++) { if (IsPinkArr[I]) { CanSetRight = false; break; } } if (CanSetRight) { for (int I = EachBlock.KaitenL; I <= EachBlock.KaitenR; I++) { IsPinkArr[I] = true; } continue; } //ブロックを配置できなかったらNG return false; } return true; } }