結果
| 問題 | No.274 The Wall |
| ユーザー |
 utaka
|
| 提出日時 | 2019-12-13 17:37:18 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,235 ms / 2,000 ms |
| コード長 | 26,623 bytes |
| コンパイル時間 | 1,640 ms |
| コンパイル使用メモリ | 117,248 KB |
| 実行使用メモリ | 210,232 KB |
| 最終ジャッジ日時 | 2024-06-22 02:34:23 |
| 合計ジャッジ時間 | 6,676 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
// ReSharper disable ArrangeTypeMemberModifiers// ReSharper disable ConvertIfStatementToSwitchStatement// ReSharper disable FunctionRecursiveOnAllPaths// ReSharper disable InconsistentNaming// ReSharper disable InlineOutVariableDeclaration// ReSharper disable InvertIf// ReSharper disable JoinDeclarationAndInitializer// ReSharper disable MemberCanBeMadeStatic.Global// ReSharper disable MemberCanBeMadeStatic.Local// ReSharper disable NonReadonlyMemberInGetHashCode// ReSharper disable PossibleNullReferenceException// ReSharper disable RedundantUsingDirective// ReSharper disable SuggestVarOrType_BuiltInTypes// ReSharper disable SuggestVarOrType_Elsewhere// ReSharper disable TailRecursiveCall// ReSharper disable UnusedMember.Global// ReSharper disable UnusedMember.Local// ReSharper disable UseObjectOrCollectionInitializert#if true && UTAKA_LOCAL//#if false#define UTAKA_DEBUG#endif//#define TOPCODERusing System;using System.Collections;using System.Collections.Generic;using System.Collections.Specialized;using System.Diagnostics;using System.IO;using System.Linq;using System.Runtime.CompilerServices;using System.Text;using System.Numerics;using System.Runtime.InteropServices;using System.Security.Cryptography;using static UtakaApp.Util;namespace UtakaApp{public partial class Program{/*https://yukicoder.me/problems/no/274*/public const string SiteName = "YukiCoder";public const string ContestName = "274";public const string ProblemName = "";public void Solve(){int N = cin.ReadInt;int M = cin.ReadInt;int[] L = new int[N];int[] R = new int[N];for (int i = 0; i < N; i++){L[i] = cin.ReadInt;R[i] = cin.ReadInt;}var g = new DirectedGraph(N * 2);for (int i = 0; i < N; i++){for (int j = 0; j < i; j++){int a = L[i];int b = R[i];int c = L[j];int d = R[j];for (int x = 0; x < 2; x++){for (int y = 0; y < 2; y++){if (CommonPoint1D(a, b, c, d)){g.AddEdge(x * N + i, (1 - y) * N + j);g.AddEdge(y * N + j, (1 - x) * N + i);}a = M - 1 - a;b = M - 1 - b;Swap(ref a, ref b);}c = M - 1 - c;d = M - 1 - d;Swap(ref c, ref d);}}}int countOfScc;int[] scc = g.StronglyConnectedComponents(out countOfScc);int num = g.N / 2;bool impossible = false;for (int i = 0; i < num; i++){if (scc[i] == scc[N + i]){impossible = true;break;}}cou.WriteLine(impossible ? "NO" : "YES");}public bool CommonPoint1D(int a, int b, int c, int d){return c <= b && a <= d;}public void Swap<T>(ref T a, ref T b){T c = a;a = b;b = c;}}public class DirectedGraph{public int N; // ノードの数public List<int>[] Adj; // AddEdgeでu,vを加えたときu->v方向で保存した向き先public List<int>[] Rev; // AddEdgeでu,vを加えたときv->u方向で保存した向き先 入次数がわかるpublic bool HasMultipleTopologicalResults; // トポロジカルソートの結果が複数ありえるかprivate List<int> topologicalResult; // トポロジカルソートした結果の順番private Stack<int> stack; // 強連結成分を求めるとき使うstackprivate int[] scc; // 強連結成分private bool[] usedInDfs; // 強連結成分を求める順方向のdfsですでに使った頂点の記録private bool[] usedInRDfs; // 強連結成分を求める逆方向のdfsですでに使った頂点の記録public DirectedGraph(int nodeCount){N = nodeCount;Adj = new List<int>[N];Rev = new List<int>[N];for (int i = 0; i < N; i++){Adj[i] = new List<int>();Rev[i] = new List<int>();}}public void AddEdge(int u, int v){Adj[u].Add(v);Rev[v].Add(u);}public bool IsDAG(){topologicalResult = topologicalResult ?? TopologicalSort();return topologicalResult.Count == N;}public List<int> TopologicalSort(){HasMultipleTopologicalResults = false;topologicalResult = new List<int>(N);var counts = new int[N]; // 処理済みの入次数var st = new Stack<int>();// 入次数が0の頂点をstackに追加for (int i = 0; i < N; i++){if (Rev[i].Count == 0){st.Push(i);}}while (st.Count > 0){// stackに1個より多くの要素があるなら、トポロジカルソートの結果は複数存在するHasMultipleTopologicalResults |= st.Count > 1;var curr = st.Pop();topologicalResult.Add(curr);foreach (int i in Adj[curr]){counts[i]++;// 入次数分の処理が終わったら、stackに加えるif (counts[i] == Rev[i].Count) st.Push(i);}}return topologicalResult;}/// <summary>/// 強連結成分分解を実行する/// </summary>/// <param name="countOfScc">強連結成分の個数</param>/// <returns>属する強連結成分のトポロジカル順序</returns>public int[] StronglyConnectedComponents(out int countOfScc){usedInDfs = new bool[N];stack = new Stack<int>();for (var i = 0; i < N; i++){if (!usedInDfs[i]){SCCDfs(i);}}scc = new int[N];for (int i = 0; i < N; i++){scc[i] = -1;}usedInRDfs = new bool[N];countOfScc = 0;while (stack.Count > 0){SCCRDfs(stack.Pop(), countOfScc++);while (stack.Count > 0 && scc[stack.Peek()] != -1){stack.Pop();}}return scc;}/// <summary>/// 強連結成分を求める順方向のDfs/// </summary>private void SCCDfs(int index){usedInDfs[index] = true;foreach (var ad in Adj[index]){if (!usedInDfs[ad]){SCCDfs(ad);}}stack.Push(index);}/// <summary>/// 強連結成分を求める逆方向のDfs/// </summary>private void SCCRDfs(int index, int topologicalOrderOfScc){scc[index] = topologicalOrderOfScc;foreach (var ad in Rev[index]){if (scc[ad] == -1){SCCRDfs(ad, topologicalOrderOfScc);}}}}//=========================================================================================// Debug IO//=========================================================================================public partial class Program{//=========================================================================================// Main//=========================================================================================private readonly ConsoleInput cin;private readonly IConsole cou;public Program(ConsoleInput cin, IConsole cou){this.cin = cin;this.cou = cou;}#if !TOPCODERpublic static void Main(string[] args){#if UTAKA_LOCAL//#if falsenew TestCaseCheckerForAtCoder().TestProblems();#elsevar cin = new ConsoleInput(System.Console.In);var console = new MyConsole();new Program(cin, console).Solve();console.Flush();#endif}#endifpublic void WriteEnumerable<T>(IEnumerable<T> A, string delimiter = " "){var sb = new StringBuilder();foreach (T v in A){sb.Append(v);sb.Append(delimiter);}if (sb.Length > 0){sb.Length--;}cou.WriteLine(sb.ToString());}}public static class Util{//=========================================================================================// Library//=========================================================================================public static T[] Array1D<T>(int a, T defaultValue)where T : struct{var ret = new T[a];for (int i = 0; i < a; i++){ret[i] = defaultValue;}return ret;}public static T[] Array1D<T>(int a)where T : struct{var ret = new T[a];return ret;}/// <summary>/// 要素数 (a, b) の、defaultValue で満たされた配列を作成します。/// </summary>/// <typeparam name="T">配列の型</typeparam>/// <param name="a">1次元の要素数</param>/// <param name="b">2次元の要素数</param>/// <param name="defaultValue">デフォルト値</param>/// <returns>指定した条件で初期化された配列</returns>public static T[,] Array2D<T>(int a, int b, T defaultValue)where T : struct{var ret = new T[a, b];for (int i = 0; i < a; i++){for (int j = 0; j < b; j++){ret[i, j] = defaultValue;}}return ret;}public static T[,,] Array3D<T>(int a, int b, int c, T defaultValue)where T : struct{T[,,] ret = new T[a, b, c];for (int i = 0; i < a; i++){for (int j = 0; j < b; j++){for (int k = 0; k < c; k++){ret[i, j, k] = defaultValue;}}}return ret;}/// <summary>/// 要素数 (a, b) の、defaultValue で満たされたJag配列を作成します。/// </summary>/// <typeparam name="T">配列の型</typeparam>/// <param name="a">1次元の要素数</param>/// <param name="b">2次元の要素数</param>/// <param name="defaultValue">デフォルト値</param>/// <returns>指定した条件で初期化された配列</returns>public static T[][] JagArray2D<T>(int a, int b, T defaultValue)where T : struct{var ret = new T[a][];for (int i = 0; i < a; i++){var row = new T[b];ret[i] = row;for (int j = 0; j < b; j++){row[j] = defaultValue;}}return ret;}/// <summary>/// 要素数 (a, b) のdefault値で満たされたJag配列を作成します。/// </summary>/// <typeparam name="T">配列の型</typeparam>/// <param name="a">1次元の要素数</param>/// <param name="b">2次元の要素数</param>/// <returns>初期化された配列</returns>public static T[][] JagArray2D<T>(int a, int b)where T : struct{var ret = new T[a][];for (int i = 0; i < a; i++){ret[i] = new T[b];}return ret;}public static T[][][] JagArray3D<T>(int a, int b, int c, T defaultValue)where T : struct{var ret = new T[a][][];for (int i = 0; i < a; i++){T[][] aRow = new T[b][];ret[i] = aRow;for (int j = 0; j < b; j++){T[] bRow = new T[c];aRow[j] = bRow;for (int k = 0; k < c; k++){bRow[k] = defaultValue;}}}return ret;}public static T[][][] JagArray3D<T>(int a, int b, int c)where T : struct{var ret = new T[a][][];for (int i = 0; i < a; i++){T[][] aRow = new T[b][];ret[i] = aRow;for (int j = 0; j < b; j++){T[] bRow = new T[c];aRow[j] = bRow;}}return ret;}public static T[][][][] JagArray4D<T>(int a, int b, int c, int d, T defaultValue)where T : struct{var ret = new T[a][][][];for (int i = 0; i < a; i++){T[][][] aRow = new T[b][][];ret[i] = aRow;for (int j = 0; j < b; j++){T[][] bRow = new T[c][];aRow[j] = bRow;for (int k = 0; k < c; k++){T[] cRow = new T[d];bRow[k] = cRow;for (int l = 0; l < d; l++){cRow[l] = defaultValue;}}}}return ret;}public static T[][][][] JagArray4D<T>(int a, int b, int c, int d)where T : struct{var ret = new T[a][][][];for (int i = 0; i < a; i++){T[][][] aRow = new T[b][][];ret[i] = aRow;for (int j = 0; j < b; j++){T[][] bRow = new T[c][];aRow[j] = bRow;for (int k = 0; k < c; k++){T[] cRow = new T[d];bRow[k] = cRow;}}}return ret;}public static T[][][][][] JagArray5D<T>(int a, int b, int c, int d, int e, T defaultValue)where T : struct{var ret = new T[a][][][][];for (int i = 0; i < a; i++){T[][][][] aRow = new T[b][][][];ret[i] = aRow;for (int j = 0; j < b; j++){T[][][] bRow = new T[c][][];aRow[j] = bRow;for (int k = 0; k < c; k++){T[][] cRow = new T[d][];bRow[k] = cRow;for (int l = 0; l < d; l++){T[] dRow = new T[e];cRow[l] = dRow;for (int m = 0; m < e; m++){dRow[m] = defaultValue;}}}}}return ret;}public static T[][][][][] JagArray5D<T>(int a, int b, int c, int d, int e)where T : struct{var ret = new T[a][][][][];for (int i = 0; i < a; i++){T[][][][] aRow = new T[b][][][];ret[i] = aRow;for (int j = 0; j < b; j++){T[][][] bRow = new T[c][][];aRow[j] = bRow;for (int k = 0; k < c; k++){T[][] cRow = new T[d][];bRow[k] = cRow;for (int l = 0; l < d; l++){T[] dRow = new T[e];cRow[l] = dRow;}}}}return ret;}/// <summary>/// ジャグ配列をコピーして返す。/// </summary>public static T[][] CopyJagArray2D<T>(T[][] source)where T : struct{int len = source.Length;T[][] dest = new T[len][];for (int i = 0; i < len; i++){T[] inner = source[i];int innerLength = inner.Length;T[] newer = new T[innerLength];Array.Copy(inner, newer, innerLength);dest[i] = newer;}return dest;}}public class IntLargeComparer : IComparer<int>{public static IntLargeComparer Instance = new IntLargeComparer();public int Compare(int x, int y){return y - x;}}public class LongLargeComparer : IComparer<long>{public static LongLargeComparer Instance = new LongLargeComparer();public int Compare(long x, long y){if (x > y) return -1;if (x < y) return 1;return 0;}}public static class UtakaExtentions{/// <summary>/// 配列をコピーします/// </summary>public static T[] Copy<T>(this IList<T> a){T[] ret = new T[a.Count];for (int i = 0; i < a.Count; i++) ret[i] = a[i];return ret;}}public class ConsoleInput{private readonly char _separator = ' ';private readonly TextReader _stream;private readonly Queue<string> inputStream;public ConsoleInput(TextReader stream, char separator = ' '){_separator = separator;_stream = stream;inputStream = new Queue<string>();}public string Read{get{if (inputStream.Count != 0){return inputStream.Dequeue();}var tmp = _stream.ReadLine().Split(_separator);for (var i = 0; i < tmp.Length; ++i){inputStream.Enqueue(tmp[i]);}return inputStream.Dequeue();}}public string ReadLine => _stream.ReadLine();public int ReadInt => int.Parse(Read);public long ReadLong => long.Parse(Read);public double ReadDouble => double.Parse(Read);public string[] ReadStrArray(long N){var ret = new string[N];for (long i = 0; i < N; ++i){ret[i] = Read;}return ret;}public int[] ReadIntArray(long N){var ret = new int[N];for (long i = 0; i < N; ++i){ret[i] = ReadInt;}return ret;}public int[] ReadIntArrayMinus1(long N){var ret = new int[N];for (long i = 0; i < N; ++i){ret[i] = ReadInt - 1;}return ret;}public long[] ReadLongArray(long N){var ret = new long[N];for (long i = 0; i < N; ++i){ret[i] = ReadLong;}return ret;}}public interface IConsole{void Flush();void Write(object obj);void Write(string str);void WriteLine(object obj);void WriteLine(string str);void WriteLine();}public class MyConsole : IConsole{public MyConsole(){var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};Console.SetOut(sw);}public void Flush(){Console.Out.Flush();}public void Write(object obj){Write(obj.ToString());}public void Write(string str){Console.Write(str);}public void WriteLine(object obj){WriteLine(obj.ToString());}public void WriteLine(string str){Console.WriteLine(str);}public void WriteLine(){Console.WriteLine();}}#if UTAKA_LOCALpublic class DebugConsole : IConsole{private readonly StringBuilder mSb;public DebugConsole(){mSb = new StringBuilder();}public void Flush(){// 何もしない}public void Write(object obj){Write(obj.ToString());}public void Write(string str){mSb.Append(str);}public void WriteLine(object obj){WriteLine(obj.ToString());}public void WriteLine(string str){mSb.AppendLine(str);}public void WriteLine(){mSb.AppendLine();}public string GetAllOutput(){return mSb.ToString();}}#endif#if UTAKA_LOCALpublic class TestCaseCheckerForAtCoder{private string GetDirectoryPath(){var problemPart = string.IsNullOrEmpty(Program.ProblemName)? "": $"/{Program.ProblemName}";return$"{Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}";}private string GetInputFilePath(int testCaseNumber){return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in";}private string GetOutputFilePath(int testCaseNumber){return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out";}public bool TestProblem(int testCaseNumber){var inputFilePath = GetInputFilePath(testCaseNumber);var outputFilePath = GetOutputFilePath(testCaseNumber);TextReader inputStream = new StreamReader(inputFilePath);var cin = new ConsoleInput(inputStream);var debugConsoleWriter = new DebugConsole();new Program(cin, debugConsoleWriter).Solve();var output = debugConsoleWriter.GetAllOutput();TextReader outputStream = new StreamReader(outputFilePath);var outputAnswer = outputStream.ReadToEnd();Dbg.WriteLine(output);Dbg.WriteLine(outputAnswer);var isCorrect = output == outputAnswer;return isCorrect;}public void TestProblems(int targetTestCaseNumber = -1){if (targetTestCaseNumber >= 0){Console.WriteLine($"!!!!!!!!!!!! Check TestCase {targetTestCaseNumber} !!!!!!!!!!");}bool isSuccessAll = true;int testCaseNumber = 0;while (true){testCaseNumber++;bool foundTargetTest = targetTestCaseNumber == testCaseNumber;if (targetTestCaseNumber >= 0 && !foundTargetTest){continue;}var inputFileName = GetInputFilePath(testCaseNumber);if (!File.Exists(inputFileName)){break;}Console.WriteLine($"TestCase {testCaseNumber} =====================================================");var result = TestProblem(testCaseNumber);if (result){Console.WriteLine("Success");}else{isSuccessAll = false;Console.WriteLine("Failure *****");}if (foundTargetTest){break;}}if (isSuccessAll){Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!");}}}#endifpublic static class Dbg{[Conditional("UTAKA_DEBUG")]public static void WriteLine(string str){Console.WriteLine(str);}[Conditional("UTAKA_DEBUG")]public static void WriteLine(){Console.WriteLine();}[Conditional("UTAKA_DEBUG")]public static void Write(string str){Console.Write(str);}}}