結果
問題 | No.3015 右に寄せろ! |
ユーザー |
![]() |
提出日時 | 2025-01-25 13:46:11 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 21,823 bytes |
コンパイル時間 | 17,082 ms |
コンパイル使用メモリ | 170,152 KB |
実行使用メモリ | 191,020 KB |
最終ジャッジ日時 | 2025-01-25 22:58:52 |
合計ジャッジ時間 | 13,223 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。 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.IO; using System.Linq; using static System.Math; using System.Text; using System.Threading; using System.Globalization; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Library; namespace Program { public static class ProblemC { static bool SAIKI = false; static public int numberOfRandomCases = 100; static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker) { var s = new List<char>(); var n = (xorshift % 10) + 1; for (var i = 0; i < n; ++i) { s.Add((xorshift % 2) == 0 ? '0' : '1'); } var ans = 0L; _input.Add(new string(s.ToArray())); while (true) { var ended = true; for (var i = 0; i < s.Count; ++i) { if (s[i] == '0') { if (i > 1) { if (s[i - 1] == '1' && s[i - 2] == '1') { s[i - 2] = '0'; s[i] = '1'; ++ans; ended = false; break; } } } } if (ended) break; } _output.Add(ans.ToString()); } static public void Solve() { var S = NS; var renzoku = 0L; var ans = 0L; foreach (var item in LIB_Common.RunLength(S)) { if (item.value == '1') { renzoku += item.count; } else { for (var i = 0;i < item.count;++i) { var cnt = renzoku / 2; ans += cnt; renzoku = cnt * 2; } } } Console.WriteLine(ans); } class Printer : StreamWriter { public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; } public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; } } static LIB_FastIO fastio = new LIB_FastIODebug(); static string[] args; static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); } static long NN => fastio.Long(); static double ND => fastio.Double(); static string NS => fastio.Scan(); static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray(); static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray(); static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray(); static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred); static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n); static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c); static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector); static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase); static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } } static IEnumerator<uint> _xsi = _xsc(); static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } } static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; } static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; } static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value); static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value); static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value); static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value); } } namespace Library { class LIB_Common { public struct RunLengthResult<T> { public long count; public T value; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public List<RunLengthResult<T>> RunLength<T>(IEnumerable<T> l) { T before = default(T); var cnt = 0; var ret = new List<RunLengthResult<T>>(); foreach (var item in l) { if (!before.Equals(item)) { if (cnt != 0) { ret.Add(new RunLengthResult<T> { count = cnt, value = before }); cnt = 0; } } before = item; ++cnt; } if (cnt != 0) ret.Add(new RunLengthResult<T> { count = cnt, value = before }); return ret; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public List<T> LCS<T>(T[] s, T[] t) where T : IEquatable<T> { int sl = s.Length, tl = t.Length; var dp = new int[sl + 1, tl + 1]; for (var i = 0; i < sl; i++) { for (var j = 0; j < tl; j++) { dp[i + 1, j + 1] = s[i].Equals(t[j]) ? dp[i, j] + 1 : Max(dp[i + 1, j], dp[i, j + 1]); } } { var r = new List<T>(); int i = sl, j = tl; while (i > 0 && j > 0) { if (s[--i].Equals(t[--j])) r.Add(s[i]); else if (dp[i, j + 1] > dp[i + 1, j]) ++j; else ++i; } r.Reverse(); return r; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public (int[] result, List<T> dp) LIS<T>(IEnumerable<T> array, bool strict) where T : IComparable<T> { var l = new List<T>(); var ret = new List<int>(); foreach (var e in array) { var left = -1; var right = l.Count; while (right - left > 1) { var mid = (right + left) / 2; if (l[mid].CompareTo(e) < 0 || !strict && l[mid].CompareTo(e) == 0) left = mid; else right = mid; } if (right == l.Count) l.Add(e); else l[right] = e; ret.Add(l.Count); } return (ret.ToArray(), l); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public (long k, T val) SanbunTansaku<T>(long left, long right, Func<long, T> fun) where T : IComparable<T> { var size = right - left; var fib = new LIB_Deque<long>(); fib.PushBack(1); fib.PushBack(1); while (fib[fib.Count - 1] * 2 + fib[fib.Count - 2] <= size) { fib.PushBack(fib[fib.Count - 1] + fib[fib.Count - 2]); } var valueLeft = left; var valueRight = right; Func<long, (bool isMax, T value)> calc = x => { if (x < valueLeft || valueRight <= x) return (true, default(T)); return (false, fun(x)); }; --left; var lv = calc(left); var m1 = left + fib.PopBack(); var m2 = m1 + fib.Back; var m1v = calc(m1); var m2v = calc(m2); var rv = calc(right = m1 - left + m1 + fib.Back); while (fib.Count > 2) { if (m1v.CompareTo(m2v) < 0) { rv = m2v; right = m2; m2v = m1v; m2 = m1; m1v = calc(m1 = left + fib.PopBack()); } else { lv = m1v; left = m1; m1v = m2v; m1 = m2; m2v = calc(m2 = left + fib.PopBack() + fib.Back); } } var ans = calc(left); for (var i = left + 1; i < right; ++i) { var na = calc(i); if (ans.CompareTo(na) > 0) { ans = na; left = i; } } return (left, ans.value); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public (double k, T val) SanbunTansaku<T>(double left, double right, Func<double, T> fun) where T : IComparable<T> { const double PHI = 0.6180339887; var lv = fun(left); var rv = fun(right); var m2 = left + (right - left) * PHI; var m2v = fun(m2); var m1 = left + (m2 - left) * PHI; var m1v = fun(m1); for (var i = 0; i < 200; ++i) { if (m1v.CompareTo(m2v) < 0) { rv = m2v; right = m2; m2v = m1v; m2 = m1; m1v = fun(m1 = left + (m2 - left) * PHI); } else { lv = m1v; left = m1; m1v = m2v; m1 = m2; m2v = fun(m2 = m1 + (m1 - left) * PHI); } } return (m1, m1v); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static public long[] NoshiBasis(long[] elementList) { var basis = new List<long>(); foreach (var item in elementList) { var e = item; foreach (var item2 in basis) { var v = e ^ item2; if (e > v) e = v; } if (e > 0) { basis.Add(e); } } var ret = new List<long>(); basis = basis.OrderByDescending(e => e).ToList(); for (var i = 0; i < basis.Count; ++i) { var v = basis[i]; for (var j = i + 1; j < basis.Count; ++j) { var v2 = v ^ basis[j]; if (v > v2) v = v2; } ret.Add(v); } return ret.ToArray(); } static public int[] MergeSort<T>(IList<T> list, int l, int r, Func<T, T, bool> leftIsSmall) { int Fill(int x) { --x; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return ++x; } var N = r - l; var ret = Enumerable.Range(0, N).ToArray(); if (N == 1) return ret; { var i = 0; var j = (N + 1) / 2; while (j < N) { if (!leftIsSmall(list[l + i], list[l + j])) { (list[l + i], list[l + j]) = (list[l + j], list[l + i]); (ret[i], ret[j]) = (ret[j], ret[i]); } ++i; ++j; } } if (N == 2) return ret; { var perm = MergeSort(list, l + (N + 1) / 2, r, leftIsSmall); var inv = Enumerable.Range(0, N / 2).ToArray(); var p = Enumerable.Range(0, N / 2).ToArray(); for (var i = 0; i < N / 2; ++i) { var j = inv[perm[i]]; if (i != j) { (list[l + i], list[l + j]) = (list[l + j], list[l + i]); (ret[i], ret[j]) = (ret[j], ret[i]); (ret[i + (N + 1) / 2], ret[j + (N + 1) / 2]) = (ret[j + (N + 1) / 2], ret[i + (N + 1) / 2]); (p[i], p[j]) = (p[j], p[i]); (inv[p[i]], inv[p[j]]) = (inv[p[j]], inv[p[i]]); } } } { var inv = Enumerable.Range(0, N + 1).ToArray(); var p = Enumerable.Range(0, N + 1).ToArray(); void Swap(int x, int y) { if (x == y) return; (list[l + x], list[l + y]) = (list[l + y], list[l + x]); (ret[x], ret[y]) = (ret[y], ret[x]); (p[x], p[y]) = (p[y], p[x]); (inv[p[x]], inv[p[y]]) = (inv[p[y]], inv[p[x]]); } void Rotate(int L, int R) { for (var i = R; --i > L;) Swap(L, i); } void BinarySearch(int X, int L, int R) { while (L + 1 < R) { var x = R - L; var y = Fill(x); var z = 3 * y / 4; var M = L + (x < z ? y / 4 : x - y / 2); if (leftIsSmall(list[l + M], list[l + X])) L = M; else R = M; } Rotate(X, R); } Rotate(0, (N + 1) / 2); var L = 1; var R = Min(3, (N + 1) / 2); var C = 8; var now = 1; while (L < (N + 1) / 2) { for (var i = R; i-- > L; ++now) { BinarySearch(i - L, (N + 1) / 2 - now - 1, inv[i + (N + 1) / 2]); } C *= 2; L = R; R = Min((C + 1) / 3, (N + 1) / 2); } } return ret; } } class LIB_Deque<T> { T[] array; int front, cap; public int Count; public T this[long i] { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { return array[GetIndex((int)i)]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] set { array[GetIndex((int)i)] = value; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_Deque(long cap = 16) { array = new T[this.cap = (int)cap]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] int GetIndex(int i) { if (i >= cap) throw new Exception(); var r = front + i; return r >= cap ? r - cap : r; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void PushFront(T x) { if (Count == cap) Extend(); if (--front < 0) front += array.Length; array[front] = x; ++Count; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T PopFront() { if (Count-- == 0) throw new Exception(); var r = array[front++]; if (front >= cap) front -= cap; return r; } public T Front => array[front]; [MethodImpl(MethodImplOptions.AggressiveInlining)] public void PushBack(T x) { if (Count == cap) Extend(); var i = front + Count++; array[i >= cap ? i - cap : i] = x; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T PopBack() { if (Count == 0) throw new Exception(); return array[GetIndex(--Count)]; } public T Back => array[GetIndex(Count - 1)]; [MethodImpl(MethodImplOptions.AggressiveInlining)] void Extend() { T[] nb = new T[cap << 1]; if (front > cap - Count) { var l = array.Length - front; Array.Copy(array, front, nb, 0, l); Array.Copy(array, 0, nb, l, Count - l); } else Array.Copy(array, front, nb, 0, Count); array = nb; front = 0; cap <<= 1; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Insert(long i, T x) { if (i > Count) throw new Exception(); this.PushFront(x); for (int j = 0; j < i; j++) this[j] = this[j + 1]; this[i] = x; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T RemoveAt(long i) { if (i < 0 || i >= Count) throw new Exception(); var r = this[i]; for (var j = i; j > 0; j--) this[j] = this[j - 1]; this.PopFront(); return r; } } class LIB_FastIO { [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIO() { str = Console.OpenStandardInput(); } readonly Stream str; readonly byte[] buf = new byte[2048]; int len, ptr; [MethodImpl(MethodImplOptions.AggressiveInlining)] byte read() { if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 2048)) <= 0) { return 0; } } return buf[ptr++]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public long Long() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = (ret << 3) + (ret << 1) + b - '0'; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } } class LIB_FastIODebug : LIB_FastIO { Queue<string> param = new Queue<string>(); [MethodImpl(MethodImplOptions.AggressiveInlining)] string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIODebug() { } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override string Scan() => NextString(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override long Long() => long.Parse(NextString()); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override double Double() => double.Parse(NextString()); } }