結果

問題 No.715 集合と二人ゲーム
ユーザー claw88claw88
提出日時 2018-07-13 23:31:45
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 8,144 bytes
コンパイル時間 1,002 ms
コンパイル使用メモリ 110,848 KB
実行使用メモリ 59,644 KB
最終ジャッジ日時 2024-10-09 05:44:28
合計ジャッジ時間 8,129 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 33 ms
18,816 KB
testcase_02 WA -
testcase_03 AC 35 ms
19,200 KB
testcase_04 WA -
testcase_05 AC 38 ms
19,840 KB
testcase_06 WA -
testcase_07 AC 42 ms
20,216 KB
testcase_08 WA -
testcase_09 AC 43 ms
20,992 KB
testcase_10 WA -
testcase_11 AC 46 ms
21,376 KB
testcase_12 WA -
testcase_13 AC 49 ms
21,612 KB
testcase_14 WA -
testcase_15 AC 51 ms
21,852 KB
testcase_16 WA -
testcase_17 AC 53 ms
22,240 KB
testcase_18 WA -
testcase_19 AC 57 ms
23,424 KB
testcase_20 WA -
testcase_21 AC 61 ms
23,752 KB
testcase_22 WA -
testcase_23 AC 61 ms
23,296 KB
testcase_24 WA -
testcase_25 AC 65 ms
24,704 KB
testcase_26 AC 65 ms
24,320 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 74 ms
25,600 KB
testcase_30 WA -
testcase_31 AC 64 ms
23,552 KB
testcase_32 WA -
testcase_33 AC 67 ms
24,448 KB
testcase_34 WA -
testcase_35 AC 27 ms
18,048 KB
testcase_36 AC 28 ms
18,048 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 27 ms
17,920 KB
testcase_40 WA -
testcase_41 AC 31 ms
18,432 KB
testcase_42 WA -
testcase_43 AC 31 ms
18,304 KB
testcase_44 WA -
testcase_45 AC 31 ms
18,432 KB
testcase_46 WA -
testcase_47 AC 31 ms
18,560 KB
testcase_48 WA -
testcase_49 AC 31 ms
18,560 KB
testcase_50 WA -
testcase_51 AC 300 ms
59,588 KB
testcase_52 WA -
testcase_53 AC 300 ms
58,544 KB
testcase_54 WA -
testcase_55 AC 298 ms
59,108 KB
testcase_56 AC 284 ms
57,076 KB
testcase_57 AC 270 ms
57,132 KB
testcase_58 WA -
testcase_59 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }

    int[] memo;
    void solve()
    {
        int N = cin.nextint;
        var A = cin.scanint;
        Array.Sort(A);
        memo = new[] { 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 2};
        var roop = new[] { 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7, 4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9 };
        //WriteLine(memo.Length);
        for (int i = 0; i < memo.Length; i++)
        {
            memo[i] = -1;
        }

        int G = 0;
        int l = 0;
        for (int i = 1; i <= A.Length; i++)
        {
            if (i == A.Length || A[i] - A[i - 1] > 1)
            {
                int r = -1;
                if (i <= 51) r = memo[i];
                else r = roop[(i - 52) % 34];
                G ^= r;
                l = i;
            }
        }
        if (G == 0) WriteLine("Second");
        else WriteLine("First");
    }

    int calc(int x)
    {
        if (memo[x] >= 0) return memo[x];

        var L = new List<int>();
        for (int i = 0; i < x / 2; i++)
        {
            if (i >= 2)
            {
                //WriteLine(i - 2 + 1);
                L.Add(calc(i - 2 + 1));
            }
            //WriteLine(x - 2 - i);
            L.Add(calc(x - i - 2));
        }
        L.Sort();
        //WriteLine(string.Join(" ", L));
        for (int i = 0; i < L.Count; i++)
        {
            if (L[i] != i) return i;
        }
        return -1;
    }
}


class Set<T>
{
    Node root;
    readonly IComparer<T> comparer;
    readonly Node nil;
    public bool IsMultiSet { get; set; }
    public Set(IComparer<T> comparer)
    {
        nil = new Node(default(T));
        root = nil;
        this.comparer = comparer;
    }
    public Set(Comparison<T> comaprison) : this(Comparer<T>.Create(comaprison)) { }
    public Set() : this(Comparer<T>.Default) { }
    public bool Add(T v)
    {
        key = v;
        return insert(ref root);
    }
    public bool Remove(T v)
    {
        key = v;
        return remove(ref root);
    }
    public T this[int index] { get { return find(root, index); } }
    public int Count { get { return root.Count; } }
    public void RemoveAt(int k)
    {
        if (k < 0 || k >= root.Count) throw new ArgumentOutOfRangeException();
        removeAt(ref root, k);
    }
    public T[] Items
    {
        get
        {
            var ret = new T[root.Count];
            var k = 0;
            walk(root, ret, ref k);
            return ret;
        }
    }
    void walk(Node t, T[] a, ref int k)
    {
        if (t.Count == 0) return;
        walk(t.lst, a, ref k);
        a[k++] = t.Key;
        walk(t.rst, a, ref k);
    }

    T key;
    bool insert(ref Node t)
    {
        if (t.Count == 0) { t = new Node(key); t.lst = t.rst = nil; t.Update(); return true; }
        var cmp = comparer.Compare(t.Key, key);
        bool res;
        if (cmp > 0)
            res = insert(ref t.lst);
        else if (cmp == 0)
        {
            if (IsMultiSet) res = insert(ref t.lst);
            else return false;
        }
        else res = insert(ref t.rst);
        balance(ref t);
        return res;
    }
    bool remove(ref Node t)
    {
        if (t.Count == 0) return false;
        var cmp = comparer.Compare(key, t.Key);
        bool ret;
        if (cmp < 0) ret = remove(ref t.lst);
        else if (cmp > 0) ret = remove(ref t.rst);
        else
        {
            ret = true;
            var k = t.lst.Count;
            if (k == 0) { t = t.rst; return true; }
            if (t.rst.Count == 0) { t = t.lst; return true; }


            t.Key = find(t.lst, k - 1);
            removeAt(ref t.lst, k - 1);
        }
        balance(ref t);
        return ret;
    }
    void removeAt(ref Node t, int k)
    {
        var cnt = t.lst.Count;
        if (cnt < k) removeAt(ref t.rst, k - cnt - 1);
        else if (cnt > k) removeAt(ref t.lst, k);
        else
        {
            if (cnt == 0) { t = t.rst; return; }
            if (t.rst.Count == 0) { t = t.lst; return; }

            t.Key = find(t.lst, k - 1);
            removeAt(ref t.lst, k - 1);
        }
        balance(ref t);
    }
    void balance(ref Node t)
    {
        var balance = t.lst.Height - t.rst.Height;
        if (balance == -2)
        {
            if (t.rst.lst.Height - t.rst.rst.Height > 0) { rotR(ref t.rst); }
            rotL(ref t);
        }
        else if (balance == 2)
        {
            if (t.lst.lst.Height - t.lst.rst.Height < 0) rotL(ref t.lst);
            rotR(ref t);
        }
        else t.Update();
    }

    T find(Node t, int k)
    {
        if (k < 0 || k > root.Count) throw new ArgumentOutOfRangeException();
        for (; ; )
        {
            if (k == t.lst.Count) return t.Key;
            else if (k < t.lst.Count) t = t.lst;
            else { k -= t.lst.Count + 1; t = t.rst; }
        }
    }
    public int LowerBound(T v)
    {
        var k = 0;
        var t = root;
        for (; ; )
        {
            if (t.Count == 0) return k;
            if (comparer.Compare(v, t.Key) <= 0) t = t.lst;
            else { k += t.lst.Count + 1; t = t.rst; }
        }
    }
    public int UpperBound(T v)
    {
        var k = 0;
        var t = root;
        for (; ; )
        {
            if (t.Count == 0) return k;
            if (comparer.Compare(t.Key, v) <= 0) { k += t.lst.Count + 1; t = t.rst; }
            else t = t.lst;
        }
    }
    void rotR(ref Node t)
    {
        var l = t.lst;
        t.lst = l.rst;
        l.rst = t;
        t.Update();
        l.Update();
        t = l;
    }
    void rotL(ref Node t)
    {
        var r = t.rst;
        t.rst = r.lst;
        r.lst = t;
        t.Update();
        r.Update();
        t = r;
    }

    class Node
    {
        public Node(T key)
        {
            Key = key;
        }
        public int Count { get; private set; }
        public sbyte Height { get; private set; }
        public T Key { get; set; }
        public Node lst, rst;
        public void Update()
        {
            Count = 1 + lst.Count + rst.Count;
            Height = (sbyte)(1 + Math.Max(lst.Height, rst.Height));
        }
        public override string ToString()
        {
            return string.Format("Count = {0}, Key = {1}", Count, Key);
        }
    }
}
class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}
0