結果
| 問題 |
No.1226 I hate Robot Arms
|
| コンテスト | |
| ユーザー |
👑  terry_u16
|
| 提出日時 | 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 - 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