結果
問題 |
No.1110 好きな歌
|
ユーザー |
![]() |
提出日時 | 2020-07-10 21:43:43 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 293 ms / 5,000 ms |
コード長 | 10,551 bytes |
コンパイル時間 | 2,532 ms |
コンパイル使用メモリ | 113,024 KB |
実行使用メモリ | 23,168 KB |
最終ジャッジ日時 | 2024-10-11 08:37:58 |
合計ジャッジ時間 | 12,625 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using YukicoderContest256.Extensions; using YukicoderContest256.Questions; namespace YukicoderContest256.Questions { public class QuestionD : AtCoderQuestionBase { public override IEnumerable<object> Solve(TextReader inputStream) { var (n, d) = inputStream.ReadValue<int, int>(); var a = new int[n]; var b = new int[n]; for (int i = 0; i < a.Length; i++) { a[i] = inputStream.ReadInt(); } a.CopyTo(b, 0); Array.Sort(b); foreach (var ai in a) { yield return SearchExtensions.GetLessEqualIndex(b, ai - d) + 1; } } } } namespace YukicoderContest256 { class Program { static void Main(string[] args) { IAtCoderQuestion question = new QuestionD(); var answers = question.Solve(Console.In); var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(writer); foreach (var answer in answers) { Console.WriteLine(answer); } Console.Out.Flush(); } } } #region Base Class namespace YukicoderContest256.Questions { public interface IAtCoderQuestion { IEnumerable<object> Solve(string input); IEnumerable<object> Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { public IEnumerable<object> Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } public abstract IEnumerable<object> Solve(TextReader inputStream); } } #endregion #region Extensions namespace YukicoderContest256.Extensions { public static class SearchExtensions { class LowerBoundComparer<T> : IComparer<T> where T : IComparable<T> { public int Compare(T x, T y) => 0 <= x.CompareTo(y) ? 1 : -1; } class UpperBoundComparer<T> : IComparer<T> where T : IComparable<T> { public int Compare(T x, T y) => 0 < x.CompareTo(y) ? 1 : -1; } // https://trsing.hatenablog.com/entry/2019/08/27/211038 public static int GetGreaterEqualIndex<T>(this ReadOnlySpan<T> span, T inclusiveMin) where T : IComparable<T> => ~span.BinarySearch(inclusiveMin, new UpperBoundComparer<T>()); public static int GetGreaterThanIndex<T>(this ReadOnlySpan<T> span, T exclusiveMin) where T : IComparable<T> => ~span.BinarySearch(exclusiveMin, new LowerBoundComparer<T>()); public static int GetLessEqualIndex<T>(this ReadOnlySpan<T> span, T inclusiveMax) where T : IComparable<T> => ~span.BinarySearch(inclusiveMax, new LowerBoundComparer<T>()) - 1; public static int GetLessThanIndex<T>(this ReadOnlySpan<T> span, T exclusiveMax) where T : IComparable<T> => ~span.BinarySearch(exclusiveMax, new UpperBoundComparer<T>()) - 1; public static int GetGreaterEqualIndex<T>(this Span<T> span, T inclusiveMin) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetGreaterEqualIndex(inclusiveMin); public static int GetGreaterThanIndex<T>(this Span<T> span, T exclusiveMin) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetGreaterThanIndex(exclusiveMin); public static int GetLessEqualIndex<T>(this Span<T> span, T inclusiveMax) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetLessEqualIndex(inclusiveMax); public static int GetLessThanIndex<T>(this Span<T> span, T exclusiveMax) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetLessThanIndex(exclusiveMax); public static int BoundaryBinarySearch(Predicate<int> predicate, int ok, int ng) { // めぐる式二分探索 while (Math.Abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static long BoundaryBinarySearch(Predicate<long> predicate, long ok, long ng) { while (Math.Abs(ok - ng) > 1) { long mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static double Bisection(Func<double, double> f, double a, double b, double eps = 1e-9) { if (f(a) * f(b) >= 0) { throw new ArgumentException("f(a)とf(b)は異符号である必要があります。"); } const int maxLoop = 100; double mid = (a + b) / 2; for (int i = 0; i < maxLoop; i++) { if (f(a) * f(mid) < 0) { b = mid; } else { a = mid; } mid = (a + b) / 2; if (Math.Abs(b - a) < eps) { break; } } return mid; } } public static class StringExtensions { public static string Join<T>(this IEnumerable<T> source) => string.Concat(source); public static string Join<T>(this IEnumerable<T> source, char separator) => string.Join(separator, source); public static string Join<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source); } public static class TextReaderExtensions { public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader)); public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader)); public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader)); public static string ReadString(this TextReader reader) => reader.ReadLine(); public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray(); public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray(); public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray(); public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator); // Supports primitive type only. public static T1 ReadValue<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1)); public static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); return (v1, v2); } public static (T1, T2, T3) ReadValue<T1, T2, T3>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); return (v1, v2, v3); } public static (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); return (v1, v2, v3, v4); } public static (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); return (v1, v2, v3, v4, v5); } public static (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); return (v1, v2, v3, v4, v5, v6); } public static (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); return (v1, v2, v3, v4, v5, v6, v7); } } } #endregion