#244898 (C#(csc)) No.5001 排他的論理和でランニング

• 問題: No.5001 排他的論理和でランニング
• ユーザー: くれちー
• 提出日時: 2018-03-16 23:43:32
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 1,484 ms / 1,500 ms
• コード長: 19,610 bytes
• コンパイル時間: 1,165 ms
• 実行使用メモリ: 49,484 KB
• スコア: 52,428,737
• 最終ジャッジ日時: 2020-03-12 19:39:17
• ジャッジサーバーID （参考情報）: judge10 /

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.5.0-beta1-19606-04 (d2bd58c6)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Convert;
using static System.Math;
using static Constants;
using static Extensions;
using static MathExtensions;

public class Program
{
    public static void Solve()
    {
        var sw = Stopwatch.StartNew();
        var n = I;
        var m = I;
        var a = Is(n);
        var rand = new Random(0);
        var inc = new SkipListSet<int>();
        var exc = new SkipListSet<int>();

        foreach (var i in Range(m))
            inc.Add(i);

        foreach (var i in Range(n - m))
            exc.Add(m + i);

        var crt = 0;
        foreach (var i in inc)
            crt ^= a[i];

        while (sw.ElapsedMilliseconds <= 1400)
        {
            var i = inc[rand.Next(inc.Count)];
            var j = exc[rand.Next(exc.Count)];
            if ((crt ^ a[i] ^ a[j]) <= crt) continue;
            crt = crt ^ a[i] ^ a[j];
            inc.Remove(i);
            inc.Add(j);
            exc.Remove(j);
            exc.Add(i);
        }

        Assert(inc.Count == m);
        foreach (var i in Range(inc.Count))
            Console.Write($"{a[inc[i]]} ");
        Console.WriteLine();
    }

    #region Scanners
    static TextScanner _ts;

    static char C => char.Parse(_ts.Next());
    static string S => _ts.Next();
    static int I => int.Parse(_ts.Next());
    static long L => long.Parse(_ts.Next());
    static BigInteger B => BigInteger.Parse(_ts.Next());
    static double D => double.Parse(_ts.Next());

    static char[] Cs(int count) => Repeat(count, () => C).ToArray();
    static string[] Ss(int count) => Repeat(count, () => S).ToArray();
    static int[] Is(int count) => Repeat(count, () => I).ToArray();
    static long[] Ls(int count) => Repeat(count, () => L).ToArray();
    static BigInteger[] Bs(int count) => Repeat(count, () => B).ToArray();
    static double[] Ds(int count) => Repeat(count, () => D).ToArray();
    #endregion

    [DebuggerStepThrough]
    public static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput());
        sw.NewLine = "\n";
#if DEBUG
        sw.AutoFlush = true;
#else
        sw.AutoFlush = false;
#endif
        Console.SetOut(sw);
        _ts = new TextScanner(Console.In);
        Solve();
        Console.Out.Flush();
    }
}

// ref. http://kaiseh.com/skiplist/SkipList.java
[DebuggerStepThrough]
class SkipList<T> : IList<T>, IReadOnlyList<T>
{
    protected class Pointer
    {
        public Pointer(Entry previous, Entry next, int distance)
        {
            this.Previous = previous;
            this.Next = next;
            this.Distance = distance;
        }

        public Entry Previous { get; set; }

        public Entry Next { get; set; }

        public int Distance { get; set; }
    }

    protected class Entry
    {
        public Entry(int level, Entry prev, Entry next, T value)
        {
            if (level > 0)
                this.Pointers = new Pointer[level];

            this.Previous = prev;
            this.Next = next;
            this.Value = value;
        }

        public Entry() { }

        public Pointer[] Pointers { get; set; }

        public Entry Previous { get; set; }

        public Entry Next { get; set; }

        public T Value { get; set; }

        public int Level => this.Pointers?.Length ?? 0;
    }

    protected class EntryEnumerator : IEnumerator<T>
    {
        private readonly SkipList<T> _base;
        private Entry _current;

        public EntryEnumerator(SkipList<T> @base, Entry current)
        {
            _base = @base;
            _current = current;
        }

        public T Current => _current.Value;

        object IEnumerator.Current => this.Current;

        public void Dispose() { }

        public bool MoveNext()
        {
            if (_current.Next == _base._head)
                return false;

            _current = _current.Next;
            return true;
        }

        public void Reset()
            => throw new NotImplementedException();
    }

    protected Entry _head;

    protected int _size;

    private int _randomSeed;

    public SkipList()
    {
        var rand = new Random();
        _randomSeed = rand.Next() | 0x100;
        BuildHead();
    }

    private void BuildHead()
    {
        _head = new Entry();
        _head.Previous = _head;
        _head.Next = _head;
    }

    private int GenerateRandomLevel()
    {
        var x = _randomSeed;
        x ^= x << 13;
        x ^= x >> 17;
        _randomSeed = x ^= x << 5;

        if ((x & 0x8001) != 0)
            return 0;

        var level = 0;
        while (((x >>= 1) & 1) != 0)
            level++;

        return level;
    }

    protected Entry AddBefore(T item, Entry entry)
    {
        var headLevel = _head.Level;
        var level = Math.Min(GenerateRandomLevel(), headLevel + 1);

        if (level > headLevel)
        {
            var pts = new Pointer[level];

            for (var i = 0; i < headLevel; i++)
                pts[i] = _head.Pointers[i];

            for (var i = headLevel; i < level; i++)
                pts[i] = new Pointer(_head, _head, 0);

            _head.Pointers = pts;
            headLevel = level;
        }

        var prev = entry.Previous;
        var next = entry;
        var e = new Entry(level, prev, next, item);
        next.Previous = e;
        prev.Next = e;

        var prevDistance = 1;
        var nextDistance = 1;

        for (var i = 0; i < level; i++)
        {
            while (prev.Pointers == null)
            {
                prevDistance++;
                prev = prev.Previous;
            }

            var lv = prev.Level;

            while (lv <= i)
            {
                var prevPt = prev.Pointers[lv - 1];
                prevDistance += prevPt.Previous.Pointers[lv - 1].Distance;
                prev = prevPt.Previous;
                lv = prev.Pointers.Length;
            }

            while (next.Pointers == null)
            {
                nextDistance++;
                next = next.Next;
            }

            lv = next.Level;

            while (lv <= i)
            {
                var nextPt = next.Pointers[lv - 1];
                nextDistance += nextPt.Distance;
                next = nextPt.Next;
                lv = next.Pointers.Length;
            }

            e.Pointers[i] = new Pointer(prev, next, nextDistance);

            prev.Pointers[i].Next = e;
            prev.Pointers[i].Distance = prevDistance;
            next.Pointers[i].Previous = e;
        }

        for (var i = level; i < headLevel; i++)
        {
            while (prev.Pointers == null)
                prev = prev.Previous;

            while (prev.Pointers.Length <= i)
                prev = prev.Pointers[prev.Pointers.Length - 1].Previous;

            prev.Pointers[i].Distance++;
        }

        _size++;
        return e;
    }

    protected Entry GetEntry(int index)
    {
        if (index < 0 || index >= _size)
            throw new IndexOutOfRangeException($"size: {_size}, index: {index}");

        var entry = _head;
        var level = entry.Level;
        var currentIndex = -1;

        while (currentIndex != index)
        {
            if (level == 0)
            {
                entry = entry.Next;
                currentIndex++;
            }
            else
            {
                var p = entry.Pointers[level - 1];
                var n = currentIndex + p.Distance;

                if (n <= index)
                {
                    entry = p.Next;
                    currentIndex = n;
                }
                else
                    level--;
            }
        }

        return entry;
    }

    protected void RemoveEntry(Entry entry)
    {
        var prev = entry.Previous;
        var next = entry.Next;
        prev.Next = next;
        next.Previous = prev;
        var level = entry.Level;

        if (level > 0)
        {
            for (var i = 0; i < level; i++)
            {
                var p = entry.Pointers[i];
                prev = p.Previous;
                next = p.Next;
                prev.Pointers[i].Next = next;
                next.Pointers[i].Previous = prev;
                prev.Pointers[i].Distance += p.Distance - 1;
            }

            prev = entry.Pointers[level - 1].Previous;
        }

        var headLevel = _head.Level;

        for (var i = level; i < headLevel; i++)
        {
            while (prev.Pointers == null)
                prev = prev.Previous;

            while (i >= prev.Pointers.Length)
                prev = prev.Pointers[prev.Pointers.Length - 1].Previous;

            prev.Pointers[i].Distance--;
        }

        _size--;
    }

    protected int GetIndex(Entry entry)
    {
        var e = entry;
        var distance = 0;

        while (e != _head)
        {
            if (e.Pointers == null)
            {
                distance++;
                e = e.Next;
            }
            else
            {
                var p = e.Pointers[e.Pointers.Length - 1];
                distance += p.Distance;
                e = p.Next;
            }
        }

        return _size - distance;
    }

    public int Count => _size;

    bool ICollection<T>.IsReadOnly => false;

    public virtual void Clear()
    {
        BuildHead();
        _size = 0;
    }

    public virtual bool Add(T item)
    {
        AddBefore(item, _head);
        return true;
    }

    public virtual void Insert(int index, T item)
    {
        if (index == _size)
            AddBefore(item, _head);
        else
        {
            var entry = GetEntry(index);
            AddBefore(item, entry);
        }
    }

    public virtual void RemoveAt(int index)
    {
        var entry = GetEntry(index);
        RemoveEntry(entry);
    }

    public virtual T this[int index]
    {
        get => GetEntry(index).Value;
        set
        {
            var entry = GetEntry(index);
            entry.Value = value;
        }
    }

    public virtual int IndexOf(T item)
    {
        var index = 0;
        var e = _head.Next;

        if (item == null)
        {
            for (; e != _head; e = e.Next, index++)
                if (e.Value == null)
                    return index;
        }
        else
        {
            for (; e != _head; e = e.Next, index++)
                if (e.Value.Equals(item))
                    return index;
        }

        return -1;
    }

    public IEnumerator<T> GetEnumerator()
        => new EntryEnumerator(this, _head);

    IEnumerator IEnumerable.GetEnumerator()
        => this.GetEnumerator();

    void ICollection<T>.Add(T item)
        => this.Add(item);

    bool ICollection<T>.Contains(T item)
        => throw new NotImplementedException();

    void ICollection<T>.CopyTo(T[] array, int arrayIndex)
        => throw new NotImplementedException();

    bool ICollection<T>.Remove(T item)
        => throw new NotImplementedException();
}

// ref. http://kaiseh.com/skiplist/SkipListSet.java
[DebuggerStepThrough]
class SkipListSet<T> : SkipList<T>
{
    private Dictionary<T, Entry> _map
        = new Dictionary<T, Entry>();

    public SkipListSet() { }

    public SkipListSet(IEnumerable<T> collection)
    {
        foreach (var item in collection)
            this.Add(item);
    }

    public override bool Add(T item)
    {
        if (_map.ContainsKey(item))
            return false;

        var entry = AddBefore(item, _head);
        _map.Add(item, entry);
        return true;
    }

    public override void Insert(int index, T item)
    {
        if (_map.ContainsKey(item))
            return;

        Entry entry;

        if (index == _size)
            entry = AddBefore(item, _head);
        else
        {
            var next = GetEntry(index);
            entry = AddBefore(item, next);
        }

        _map.Add(item, entry);
    }

    public override T this[int index]
    {
        set
        {
            var entry = GetEntry(index);
            var oldValue = entry.Value;
            entry.Value = value;
            _map.Remove(oldValue);
            _map.Add(value, entry);
        }
    }

    public override void Clear()
    {
        base.Clear();
        _map.Clear();
    }

    public bool Contains(T item)
        => _map.ContainsKey(item);

    public override int IndexOf(T item)
    {
        _map.TryGetValue(item, out var entry);

        if (entry == null)
            return -1;

        return GetIndex(entry);
    }

    public bool Remove(T item)
    {
        _map.TryGetValue(item, out var entry);

        if (entry == null)
            return false;

        RemoveEntry(entry);
        _map.Remove(item);
        return true;
    }

    public override void RemoveAt(int index)
    {
        var item = this[index];
        Remove(item);
    }
}

[DebuggerStepThrough]
public class TextScanner
{
    private readonly TextReader _tr;

    public TextScanner(TextReader tr)
    {
        _tr = tr;
    }

    public string Next()
    {
        var sb = new StringBuilder();
        int i;
        do
        {
            i = _tr.Read();
            if (i == -1) throw new EndOfStreamException();
        }
        while (char.IsWhiteSpace((char)i));
        while (i != -1 && !char.IsWhiteSpace((char)i))
        {
            sb.Append((char)i);
            i = _tr.Read();
        }
        return sb.ToString();
    }
}

public static class Constants
{
    public const int AnswerToLifeTheUniverseAndEverything = 42;
    public const string Yes = "Yes";
    public const string No = "No";
    public const string YES = "YES";
    public const string NO = "NO";
    public const string Possible = "Possible";
    public const string Impossible = "Impossible";
    public const string POSSIBLE = "POSSIBLE";
    public const string IMPOSSIBLE = "IMPOSSIBLE";
}

[DebuggerStepThrough]
public static class Extensions
{
    public static void Answer(object value)
    {
        Console.WriteLine(value);
        Exit(0);
    }

    public static void Assert(bool condition)
    {
        if (!condition) throw new Exception("Assertion failed");
    }

    public static string AsString(this IEnumerable<char> source) => new string(source.ToArray());

    public static Dictionary<T, int> Bucket<T>(this IEnumerable<T> source) where T : IEquatable<T>
    {
        var dict = new Dictionary<T, int>();
        foreach (var item in source) if (dict.ContainsKey(item)) dict[item]++; else dict[item] = 1;
        return dict;
    }

    public static int[] Bucket<T>(this IEnumerable<T> source, int maxValue, Func<T, int> selector)
    {
        var arr = new int[maxValue + 1];
        foreach (var item in source) arr[selector(item)]++;
        return arr;
    }

    public static IComparer<T> CreateDescendingComparer<T>()
        where T : IComparable<T>
        => Comparer<T>.Create((x, y) => y.CompareTo(x));

    public static IEnumerable<int> CumSum(this IEnumerable<int> source)
    {
        var sum = 0;
        foreach (var item in source) yield return sum += item;
    }

    public static IEnumerable<long> CumSum(this IEnumerable<long> source)
    {
        var sum = 0L;
        foreach (var item in source) yield return sum += item;
    }

    public static void Exit(int exitCode)
    {
        Console.Out.Flush();
        Environment.Exit(exitCode);
    }

    public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
    {
        foreach (var item in source) action(item);
    }

    public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, _> func)
    {
        foreach (var item in source) func(item);
    }

    public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action)
    {
        var i = 0;
        foreach (var item in source) action(item, i++);
    }

    public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, int, _> func)
    {
        var i = 0;
        foreach (var item in source) func(item, i++);
    }

    // [l, r)
    public static bool IsIn<T>(this T value, T l, T r)
        where T : IComparable<T>
    {
        if (l.CompareTo(r) > 0) throw new ArgumentException();
        return l.CompareTo(value) <= 0 && value.CompareTo(r) < 0;
    }

    public static IEnumerable<int> Range(int start, int end, int step = 1)
    {
        for (var i = start; i < end; i += step) yield return i;
    }

    public static IEnumerable<int> Range(int end) => Range(0, end);

    public static void Repeat(int count, Action action)
    {
        for (var i = 0; i < count; i++) action();
    }

    public static void Repeat(int count, Action<int> action)
    {
        for (var i = 0; i < count; i++) action(i);
    }

    public static IEnumerable<T> Repeat<T>(int count, Func<T> func)
    {
        for (var i = 0; i < count; i++) yield return func();
    }

    public static IEnumerable<T> Repeat<T>(int count, Func<int, T> func)
    {
        for (var i = 0; i < count; i++) yield return func(i);
    }

    public static IEnumerable<int> RangeReverse(int start, int end, int step = 1)
    {
        for (var i = end - 1; i >= start; i -= step) yield return i;
    }

    public static IEnumerable<int> RangeReverse(int end) => RangeReverse(0, end);

    public static void Swap<T>(ref T x, ref T y)
    {
        var tmp = x; x = y; y = tmp;
    }
}

[DebuggerStepThrough]
public static class MathExtensions
{
    public static int DivCeil(int left, int right)
        => left / right + (left % right == 0 ? 0 : 1);

    public static long DivCeil(long left, long right)
        => left / right + (left % right == 0L ? 0L : 1L);

    public static int Gcd(int left, int right)
    {
        int r;
        while ((r = left % right) != 0) { left = right; right = r; }
        return right;
    }

    public static long Gcd(long left, long right)
    {
        long r;
        while ((r = left % right) != 0L) { left = right; right = r; }
        return right;
    }

    public static BigInteger Gcd(BigInteger left, BigInteger right)
        => BigInteger.GreatestCommonDivisor(left, right);

    public static int HighestOneBit(int x)
    {
        x |= x >> 01;
        x |= x >> 02;
        x |= x >> 04;
        x |= x >> 08;
        x |= x >> 16;
        return x - (x >> 1);
    }

    public static long HighestOneBit(long x)
    {
        x |= x >> 01;
        x |= x >> 02;
        x |= x >> 04;
        x |= x >> 08;
        x |= x >> 16;
        x |= x >> 32;
        return x - (x >> 1);
    }

    public static int Lcm(int left, int right) => left / Gcd(left, right) * right;

    public static long Lcm(long left, long right) => left / Gcd(left, right) * right;

    public static BigInteger Lcm(BigInteger left, BigInteger right)
        => left / Gcd(left, right) * right;

    public static int Pow(int value, int exponent)
    {
        var r = 1;
        while (exponent > 0)
        {
            if ((exponent & 1) == 1) r *= value;
            value *= value;
            exponent >>= 1;
        }
        return r;
    }

    public static long Pow(long value, int exponent)
    {
        var r = 1L;
        while (exponent > 0)
        {
            if ((exponent & 1) == 1) r *= value;
            value *= value;
            exponent >>= 1;
        }
        return r;
    }

    public static long Fact(int value)
    {
        var r = 1L;
        for (var i = 2; i <= value; i++) r *= i;
        return r;
    }
}