結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 30 ms
24,020 KB |
| testcase_01 | AC | 30 ms
23,896 KB |
| testcase_02 | AC | 29 ms
26,232 KB |
| testcase_03 | AC | 467 ms
129,244 KB |
| testcase_04 | AC | 30 ms
23,948 KB |
| testcase_05 | AC | 30 ms
24,364 KB |
| testcase_06 | AC | 30 ms
26,116 KB |
| testcase_07 | AC | 29 ms
24,112 KB |
| testcase_08 | AC | 29 ms
24,152 KB |
| testcase_09 | AC | 30 ms
24,020 KB |
| testcase_10 | AC | 30 ms
23,900 KB |
| testcase_11 | AC | 1,235 ms
210,232 KB |
| testcase_12 | AC | 107 ms
23,984 KB |
| testcase_13 | AC | 31 ms
24,112 KB |
| testcase_14 | AC | 45 ms
24,024 KB |
| testcase_15 | AC | 66 ms
24,156 KB |
| testcase_16 | AC | 360 ms
85,804 KB |
| testcase_17 | AC | 333 ms
84,920 KB |
| testcase_18 | AC | 360 ms
82,476 KB |
| testcase_19 | AC | 100 ms
24,240 KB |
| testcase_20 | AC | 110 ms
24,324 KB |
| testcase_21 | AC | 114 ms
22,168 KB |
| testcase_22 | AC | 120 ms
24,116 KB |
| testcase_23 | AC | 118 ms
21,944 KB |
| testcase_24 | AC | 120 ms
24,124 KB |
| testcase_25 | AC | 119 ms
26,160 KB |
コンパイルメッセージ
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 TOPCODER
using 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; // 強連結成分を求めるとき使うstack
private 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 !TOPCODER
public static void Main(string[] args)
{
#if UTAKA_LOCAL
//#if false
new TestCaseCheckerForAtCoder().TestProblems();
#else
var cin = new ConsoleInput(System.Console.In);
var console = new MyConsole();
new Program(cin, console).Solve();
console.Flush();
#endif
}
#endif
public 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_LOCAL
public 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_LOCAL
public 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 !!!!!!!!!");
}
}
}
#endif
public 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);
}
}
}