結果
問題 | No.576 E869120 and Rings |
ユーザー |
![]() |
提出日時 | 2022-12-31 11:05:14 |
言語 | C# (.NET 8.0.404) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,344 bytes |
コンパイル時間 | 14,971 ms |
コンパイル使用メモリ | 165,308 KB |
実行使用メモリ | 191,716 KB |
最終ジャッジ日時 | 2024-11-26 09:28:43 |
合計ジャッジ時間 | 31,647 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 MLE * 1 |
other | AC * 27 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (99 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using System.Collections.Generic;using System.Linq;class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();if (InputPattern == "Input1") {WillReturn.Add("8 4");WillReturn.Add("11101110");//0.857142857142857}else if (InputPattern == "Input2") {WillReturn.Add("8 4");WillReturn.Add("11011001");//0.833333333333333}else if (InputPattern == "Input3") {WillReturn.Add("10 4");WillReturn.Add("1001001001");//0.6}else if (InputPattern == "Input4") {return System.IO.File.ReadAllLines(@"D:\CSharp\TestConsole\test_in\in01.txt").ToList();}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}static int mN;static int mK;static double[] mAArr;static void Main(){//var sw = System.Diagnostics.Stopwatch.StartNew();List<string> InputList = GetInputList();int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();mN = wkArr[0];mK = wkArr[1];mCompareArr = new double[mN * 2];mRunSumArr = new double[mN * 2];string AStr = InputList[1];mAArr = new double[mN];bool HasZero = false;for (int I = 0; I <= AStr.Length - 1; I++) {if (AStr[I] == '0') {mAArr[I] = 0D;HasZero = true;}if (AStr[I] == '1') mAArr[I] = 1D;}// 全て1の場合if (HasZero == false) {Console.WriteLine(1);return;}// 答えで二分探索double L = 0;double R = 1;while (L + 0.0000001 < R) {double Mid = (L + R) / 2;bool Result = CanAchieve(Mid);if (Result) {L = Mid;}else {R = Mid;}}Console.WriteLine(R);//Console.WriteLine(sw.Elapsed);}static double[] mCompareArr;static double[] mRunSumArr;// NeedAVGを達成できるかを判定static bool CanAchieve(double pNeedAVG){for (int I = 1; I <= 2; I++) {for (int J = 0; J <= mAArr.GetUpperBound(0); J++) {mCompareArr[J + mN * (I - 1)] = mAArr[J] - pNeedAVG;}}int UB = mCompareArr.GetUpperBound(0);// 累積和を設定するfor (int I = 0; I <= UB; I++) {mRunSumArr[I] = mCompareArr[I];if (0 < I) {mRunSumArr[I] += mRunSumArr[I - 1];}}var InsDeque = new Deque<int>();// 終端を全探索bool FirstFlag = true;int PrevRangeEnd = -1;for (int I = 0; I <= UB; I++) {// 長さKの区間を取れなければcontinueif (I - mK + 1 < 0) continue;// 始点候補のStaint RangeSta = I - mN + 1;RangeSta = Math.Max(0, RangeSta);// 始点候補のEndint RangeEnd = I - mK + 1;if (FirstFlag) {FirstFlag = false;}else {RangeSta = Math.Max(RangeSta, PrevRangeEnd + 1);}// 引退処理while (InsDeque.Count > 0) {int FrontInd = InsDeque[0];if (RangeSta <= FrontInd && FrontInd <= RangeEnd == false) {InsDeque.PopFront();continue;}break;}for (int J = RangeSta; J <= RangeEnd; J++) {// 押し出し処理while (InsDeque.Count > 0) {int LastInd = InsDeque[InsDeque.Count - 1];if (mRunSumArr[LastInd] - mCompareArr[LastInd] > mRunSumArr[J] - mCompareArr[J]) {InsDeque.PopBack();continue;}break;}// 追加処理InsDeque.PushBack(J);}PrevRangeEnd = RangeEnd;// 最小値double MinVal = mRunSumArr[InsDeque[0]] - mCompareArr[InsDeque[0]];if (mRunSumArr[I] - MinVal >= 0) return true;}return false;}}#region Dequeinternal class Deque<T>{T[] buf;int offset, count, capacity;internal int Count { get { return count; } }internal Deque(int cap) { buf = new T[capacity = cap]; }internal Deque() { buf = new T[capacity = 16]; }internal T this[int index]{get { return buf[GetIndex(index)]; }set { buf[GetIndex(index)] = value; }}private int GetIndex(int index){if (index >= capacity)throw new IndexOutOfRangeException("out of range");int ret = index + offset;if (ret >= capacity)ret -= capacity;return ret;}internal void PushFront(T item){if (count == capacity) Extend();if (--offset < 0) offset += buf.Length;buf[offset] = item;count++;}internal T PopFront(){if (count == 0)throw new InvalidOperationException("collection is empty");count--;T ret = buf[offset++];if (offset >= capacity) offset -= capacity;return ret;}internal void PushBack(T item){if (count == capacity) Extend();int id = count + offset;count++;if (id >= capacity) id -= capacity;buf[id] = item;}internal T PopBack(){if (count == 0)throw new InvalidOperationException("collection is empty");return buf[GetIndex(--count)];}internal void Insert(int index, T item){if (index > count) throw new IndexOutOfRangeException();this.PushFront(item);for (int i = 0; i < index; i++)this[i] = this[i + 1];this[index] = item;}internal T RemoveAt(int index){if (index < 0 || index >= count) throw new IndexOutOfRangeException();T ret = this[index];for (int i = index; i > 0; i--)this[i] = this[i - 1];this.PopFront();return ret;}private void Extend(){T[] newBuffer = new T[capacity << 1];if (offset > capacity - count) {int len = buf.Length - offset;Array.Copy(buf, offset, newBuffer, 0, len);Array.Copy(buf, 0, newBuffer, len, count - len);}else Array.Copy(buf, offset, newBuffer, 0, count);buf = newBuffer;offset = 0;capacity <<= 1;}internal T[] Items//デバッグ時に中身を調べるためのプロパティ{get{T[] a = new T[count];for (int i = 0; i < count; i++)a[i] = this[i];return a;}}}#endregion