結果

問題 No.1226 I hate Robot Arms
ユーザー 👑 terry_u16terry_u16
提出日時 2020-09-11 22:06:52
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 968 ms / 2,000 ms
コード長 16,571 bytes
コンパイル時間 5,658 ms
コンパイル使用メモリ 116,128 KB
実行使用メモリ 42,360 KB
最終ジャッジ日時 2023-08-30 09:54:06
合計ジャッジ時間 30,136 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
24,532 KB
testcase_01 AC 81 ms
26,556 KB
testcase_02 AC 336 ms
31,680 KB
testcase_03 AC 388 ms
35,060 KB
testcase_04 AC 415 ms
38,256 KB
testcase_05 AC 381 ms
38,732 KB
testcase_06 AC 896 ms
38,656 KB
testcase_07 AC 329 ms
29,736 KB
testcase_08 AC 158 ms
38,316 KB
testcase_09 AC 641 ms
31,068 KB
testcase_10 AC 144 ms
29,228 KB
testcase_11 AC 463 ms
42,360 KB
testcase_12 AC 290 ms
35,512 KB
testcase_13 AC 234 ms
40,864 KB
testcase_14 AC 770 ms
33,208 KB
testcase_15 AC 128 ms
34,564 KB
testcase_16 AC 869 ms
40,948 KB
testcase_17 AC 291 ms
31,336 KB
testcase_18 AC 224 ms
33,336 KB
testcase_19 AC 467 ms
38,504 KB
testcase_20 AC 444 ms
40,448 KB
testcase_21 AC 581 ms
40,144 KB
testcase_22 AC 920 ms
37,028 KB
testcase_23 AC 890 ms
40,848 KB
testcase_24 AC 902 ms
39,048 KB
testcase_25 AC 897 ms
40,840 KB
testcase_26 AC 911 ms
38,884 KB
testcase_27 AC 968 ms
39,076 KB
testcase_28 AC 961 ms
38,996 KB
testcase_29 AC 962 ms
38,992 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using YukicoderContest265.Extensions;
using YukicoderContest265.Questions;
using System.Numerics;

namespace YukicoderContest265.Questions
{
    public class QuestionD : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var (n, queries) = inputStream.ReadValue<int, int>();

            var segTree = new LazySegmentTree<Arm, Operation>(Enumerable.Repeat(new Arm(Complex.One), n).ToArray());
            var angles = new double[n];

            for (int q = 0; q < queries; q++)
            {
                var input = inputStream.ReadIntArray();
                var kind = input[0];
                var index = input[1];

                // 双対セグ木を持っていない
                if (kind == 0)
                {
                    index--;
                    var currentAngle = angles[index];
                    var targetAngle = input[2]  * Math.PI * 2 / 360;
                    segTree.Update(index, n, new Operation(Complex.FromPolarCoordinates(1, targetAngle - currentAngle)));
                    angles[index] = targetAngle;
                }
                else if (kind == 1)
                {
                    index--;
                    var currentLength = segTree.Query(index, index + 1).Value.Magnitude;
                    var targetLength = input[2];
                    segTree.Update(index, index + 1, new Operation(new Complex(targetLength / currentLength, 0)));
                }
                else
                {
                    var coordinate = segTree.Query(0, index).Value;
                    yield return $"{coordinate.Real} {coordinate.Imaginary}";
                }
            }
        }

        readonly struct Arm : IMonoid<Arm>
        {
            public Complex Value { get; }

            public Arm Identity => new Arm(Complex.Zero);

            public Arm(Complex value)
            {
                Value = value;
            }

            public Arm Multiply(Arm other) => new Arm(Value + other.Value);
            public override string ToString() => Value.ToString();
        }

        readonly struct Operation : IMonoidWithAct<Arm, Operation>, IEquatable<Operation>
        {
            public Complex Value { get; }

            public Operation Identity => new Operation(Complex.One);

            public Operation(Complex value)
            {
                Value = value;
            }

            public Arm Act(Arm monoid) => new Arm(Value * monoid.Value);

            public Operation Multiply(Operation other) => new Operation(Value * other.Value);

            public override bool Equals(object obj)
            {
                return obj is Operation rotator && Equals(rotator);
            }

            public bool Equals(Operation other)
            {
                return Value.Equals(other.Value);
            }

            public override int GetHashCode()
            {
                return HashCode.Combine(Value);
            }

            public static bool operator ==(Operation left, Operation right)
            {
                return left.Equals(right);
            }

            public static bool operator !=(Operation left, Operation right)
            {
                return !(left == right);
            }

            public override string ToString() => Value.ToString();
        }

        public interface ISemigroup<TSet> where TSet : ISemigroup<TSet>
        {
            public TSet Multiply(TSet other);
        }

        public interface IMonoid<TSet> : ISemigroup<TSet> where TSet : IMonoid<TSet>, new()
        {
            public TSet Identity { get; }
        }

        public interface IMonoidWithAct<TMonoid, TOperator> : IMonoid<TOperator>
            where TMonoid : IMonoid<TMonoid>, new()
            where TOperator : IMonoid<TOperator>, new()
        {
            public TMonoid Act(TMonoid monoid);
        }

        public class LazySegmentTree<TMonoid, TOperator>
        where TMonoid : IMonoid<TMonoid>, new()
        where TOperator : IMonoidWithAct<TMonoid, TOperator>, IEquatable<TOperator>, new()
        {
            private readonly TMonoid[] _data;
            private readonly TOperator[] _lazy;
            private readonly TMonoid _monoidIdenty;
            private readonly TOperator _operatorIdentity;

            private readonly int _leafOffset;  // n - 1
            private readonly int _leafLength;  // n (= 2^k)

            public int Length { get; }

            public LazySegmentTree(ICollection<TMonoid> data)
            {
                Length = data.Count;
                _leafLength = GetMinimumPow2(data.Count);
                _leafOffset = _leafLength - 1;
                _data = new TMonoid[_leafOffset + _leafLength];
                _monoidIdenty = new TMonoid().Identity;
                _operatorIdentity = new TOperator().Identity;

                data.CopyTo(_data, _leafOffset);
                BuildTree();
                _lazy = Enumerable.Repeat(_operatorIdentity, _data.Length).ToArray();
            }

            private void LazyEvaluate(int index)
            {
                if (_lazy[index].Equals(_operatorIdentity))
                {
                    return;
                }
                else if (index < _leafOffset) // 葉でない場合は子に伝播
                {
                    var left = (index << 1) + 1;
                    var right = left + 1;
                    _lazy[left] = _lazy[index].Multiply(_lazy[left]);
                    _lazy[right] = _lazy[index].Multiply(_lazy[right]);
                }

                // 自身を更新
                _data[index] = _lazy[index].Act(_data[index]);
                _lazy[index] = _operatorIdentity;
            }

            public void Update(int begin, int end, TOperator op)
            {
                if (begin < 0)
                {
                    throw new ArgumentOutOfRangeException(nameof(begin));
                }
                if (end > Length)
                {
                    throw new ArgumentOutOfRangeException(nameof(end));
                }
                if (begin >= end)
                {
                    throw new ArgumentException($"{nameof(end)} must be grater than {nameof(begin)}");
                }
                Update(begin, end, op, 0, 0, _leafLength);
            }

            private void Update(int begin, int end, TOperator op, int index, int left, int right)
            {
                LazyEvaluate(index);
                if (begin <= left && right <= end) // 全部含まれる
                {
                    _lazy[index] = _lazy[index].Multiply(op);
                    LazyEvaluate(index);
                }
                else if (begin < right && left < end) // 一部だけ含まれる
                {
                    var l = (index << 1) + 1;
                    var r = l + 1;
                    Update(begin, end, op, l, left, (left + right) / 2);
                    Update(begin, end, op, r, (left + right) / 2, right);
                    _data[index] = _data[l].Multiply(_data[r]);
                }
            }

            public TMonoid Query(int begin, int end)
            {
                if (begin < 0)
                {
                    throw new ArgumentOutOfRangeException(nameof(begin));
                }
                if (end > Length)
                {
                    throw new ArgumentOutOfRangeException(nameof(end));
                }
                if (begin >= end)
                {
                    throw new ArgumentException($"{nameof(end)} must be grater than {nameof(begin)}");
                }
                return Query(begin, end, 0, 0, _leafLength);
            }

            private TMonoid Query(int begin, int end, int index, int left, int right)
            {
                LazyEvaluate(index);
                if (right <= begin || end <= left)      // 範囲外
                {
                    return _monoidIdenty;
                }
                else if (begin <= left && right <= end) // 全部含まれる
                {
                    return _data[index];
                }
                else    // 一部だけ含まれる
                {
                    var l = (index << 1) + 1;
                    var r = l + 1;
                    var leftValue = Query(begin, end, l, left, (left + right) / 2);     // 左の子
                    var rightValue = Query(begin, end, r, (left + right) / 2, right);   // 右の子
                    return leftValue.Multiply(rightValue);
                }
            }

            private void BuildTree()
            {
                foreach (ref var unusedLeaf in _data.AsSpan()[(_leafOffset + Length)..])
                {
                    unusedLeaf = _monoidIdenty;  // 単位元埋め
                }

                for (int i = _leafLength - 2; i >= 0; i--)  // 葉の親から順番に一つずつ上がっていく
                {
                    var left = (i << 1) + 1;
                    var right = left + 1;
                    _data[i] = _data[left].Multiply(_data[right]); // f(left, right)
                }
            }

            private int GetMinimumPow2(int n)
            {
                var p = 1;
                while (p < n)
                {
                    p <<= 1;
                }
                return p;
            }
        }

    }
}

namespace YukicoderContest265
{
    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 YukicoderContest265.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 YukicoderContest265.Extensions
{
    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);
        }

        public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue<T1, T2, T3, T4, T5, T6, T7, T8>(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));
            var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8));
            return (v1, v2, v3, v4, v5, v6, v7, v8);
        }
    }
}

#endregion
0