結果
問題 | No.1226 I hate Robot Arms |
ユーザー |
![]() |
提出日時 | 2020-09-11 22:06:52 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 791 ms / 2,000 ms |
コード長 | 16,571 bytes |
コンパイル時間 | 2,799 ms |
コンパイル使用メモリ | 122,928 KB |
実行使用メモリ | 43,344 KB |
最終ジャッジ日時 | 2025-01-01 21:05:26 |
合計ジャッジ時間 | 21,339 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
コンパイルメッセージ
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 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 - 1private 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 Classnamespace 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 Extensionsnamespace 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