結果

問題 No.2165 Let's Play Nim!
ユーザー fgwiebfaoish
提出日時 2022-12-16 01:57:45
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 14,685 bytes
コンパイル時間 2,127 ms
コンパイル使用メモリ 122,780 KB
実行使用メモリ 68,016 KB
平均クエリ数 395.28
最終ジャッジ日時 2024-11-14 18:21:01
合計ジャッジ時間 21,354 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 11 RE * 20 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using nint=System.Int32;
static class Program {
    const long inf = long.MaxValue>>1;
    const int mod = 998244353;
    static Sc sc = new Sc();
    static void Main() {
        Pt pt = new Pt(Solve);
        pt.Sm();
    }
    static void Solve(Pt pt) {
        var n = sc.I;
        var a = sc.Ia2;
        int g = 0;
        int m = 25;
        var avl = new Avl[m];
        var avl2 = new Avl[75001];
        for(int i = 0;i<avl2.Length;i++) {
            avl2[i]=new Avl();
        }
        for(int i = 0;i<m;i++) {
            avl[i]=new Avl();
        }
        for(int i = 1;i<=n;i++) {
            g^=a[i];
            for(int j = 0;j<m;j++) {
                if(((1<<j)&a[i])!=0) {
                    avl[j].Ud(a[i]);
                    avl2[a[i]].Ud(i);
                }
            }
        }
        Console.WriteLine(g==0?0:1);
        if(g!=0) { Fu(); }
        while(true) {
            var (i, k)=sc.Tp2<int>();
            var z = sc.I;
            if(z==-1) { break; }
            Fo(i,k);
            z=Fu();
            if(z==-1) { break; }
        }
        int Fu() {
            var l = (int)Log(g,2);
            var e = avl[l].Ra(1);
            var d = e.n^g;
            d=e.n-d;
            var p = avl2[e.n].Ra(1).n;
            Console.WriteLine("{0} {1}",p,d);
            Fo(p,d);
            return sc.I;
        }
        void Fo(int i,int k) {
            for(int j = 0;j<m;j++) {
                if((a[i]&(1<<j))!=0) { avl[j].Dl(a[i]); }
            }
            avl2[a[i]].Dl(i);
            g^=a[i];
            a[i]-=k;
            g^=a[i];
            avl2[a[i]].Ud(i);
            for(int j = 0;j<m;j++) {
                if((a[i]&(1<<j))!=0) { avl[j].Ud(a[i]); }
            }
        }
    }
}
public class Avl {
    public class Nd {
        public int h = 1, c = 1;
        public readonly nint n;
        public Nd l, r;
        public Nd(nint n,Nd du) { this.n=n; l=du; r=du; }
    }
    public Nd root, du;
    public int cnt = 0;
    public Avl() {
        du=new Nd(nint.MinValue,du); du.h=0; du.c=0;
        root=du;
    }
    public Avl(Avl z) {
        du=new Nd(nint.MinValue,du); du.h=0; du.c=0;
        root=Fu(z.root);
        cnt=z.cnt;
        Nd Fu(Nd nd) {
            if(nd.h==0) { return du; }
            Nd mn = new Nd(nd.n,du);
            mn.h=nd.h;
            mn.c=nd.c;
            mn.l=Fu(nd.l);
            mn.r=Fu(nd.r);
            return mn;
        }
    }
    public void Ud(nint n) {
        Nd mn = new Nd(n,du);
        if(root==du) { root=mn; }
        else {
            Fu(root,mn);
            if(Abs(root.l.h-root.r.h)>1) { root=Rotate(root); }
        }
        cnt++;
    }
    private void Fu(Nd t,Nd mn) {
        t.c++;
        if(t.n>mn.n) {
            if(t.l!=du) {
                Fu(t.l,mn);
                if(Abs(t.l.l.h-t.l.r.h)>1) { t.l=Rotate(t.l); }
            }
            else { t.l=mn; }
        }
        else {
            if(t.r!=du) {
                Fu(t.r,mn);
                if(Abs(t.r.l.h-t.r.r.h)>1) { t.r=Rotate(t.r); }
            }
            else { t.r=mn; }
        }
        t.h=Max(t.l.h,t.r.h)+1;
    }
    private Nd Rotate(Nd t) {
        Nd nd = du;
        if(t.l.h>t.r.h) {
            if(t.l.l.h>t.l.r.h) {
                nd=t.l; t.l=t.l.r; nd.r=t;
                t.h=Max(t.l.h,t.r.h)+1;
                t.c=t.l.c+t.r.c+1;
            }
            else {
                nd=t.l.r;
                t.l.r=nd.l; nd.l=t.l;
                t.l.h=Max(t.l.l.h,t.l.r.h)+1;
                t.l.c=t.l.l.c+t.l.r.c+1;
                t.l=nd.r; nd.r=t;
                t.h=Max(t.l.h,t.r.h)+1;
                t.c=t.l.c+t.r.c+1;
            }
        }
        else {
            if(t.r.l.h>t.r.r.h) {
                nd=t.r.l;
                t.r.l=nd.r; nd.r=t.r;
                t.r.h=Max(t.r.l.h,t.r.r.h)+1;
                t.r.c=t.r.l.c+t.r.r.c+1;
                t.r=nd.l; nd.l=t;
                t.h=Max(t.l.h,t.r.h)+1;
                t.c=t.l.c+t.r.c+1;
            }
            else {
                nd=t.r; t.r=t.r.l; nd.l=t;
                t.h=Max(t.l.h,t.r.h)+1;
                t.c=t.l.c+t.r.c+1;
            }
        }
        nd.h=Max(nd.l.h,nd.r.h)+1;
        nd.c=nd.l.c+nd.r.c+1;
        return nd;
    }
    public bool Dl(nint n) {
        if(cnt==0) { return false; }
        Nd t = root;
        if(t.n==n) {
            root=Fd2(root);
            if(cnt==0) { return true; }
            else if(Abs(root.l.h-root.r.h)>1) { root=Rotate(root); }
            else {
                root.h=Max(root.l.h,root.r.h)+1;
                root.c=root.l.c+root.r.c+1;
            }
            return true;
        }
        bool bo = Fd1(root,n);
        if(Abs(root.l.h-root.r.h)>1) { root=Rotate(root); }
        else {
            root.h=Max(root.l.h,root.r.h)+1;
            root.c=root.l.c+root.r.c+1;
        }
        return bo;
    }
    private bool Fd1(Nd t,nint n) {
        if(t.n>n) {
            if(t.l==du) { return false; }
            else if(t.l.n!=n) {
                bool bo = Fd1(t.l,n);
                if(Abs(t.l.l.h-t.l.r.h)>1) { t.l=Rotate(t.l); }
                else {
                    t.l.h=Max(t.l.l.h,t.l.r.h)+1;
                    t.l.c=t.l.l.c+t.l.r.c+1;
                }
                return bo;
            }
            else {
                t.l=Fd2(t.l);
                t.h=Max(t.l.h,t.r.h)+1;
                t.c=t.l.c+t.r.c+1;
                return true;
            }
        }
        else {
            if(t.r==du) { return false; }
            else if(t.r.n!=n) {
                bool bo = Fd1(t.r,n);
                if(Abs(t.r.l.h-t.r.r.h)>1) { t.r=Rotate(t.r); }
                else {
                    t.r.h=Max(t.r.l.h,t.r.r.h)+1;
                    t.r.c=t.r.l.c+t.r.r.c+1;
                }
                return bo;
            }
            else {
                t.r=Fd2(t.r);
                t.h=Max(t.l.h,t.r.h)+1;
                t.c=t.l.c+t.r.c+1;
                return true;
            }
        }
    }
    private Nd Fd2(Nd dn) {
        cnt--;
        if(dn.l==du) { return dn.r; }
        if(dn.r==du) { return dn.l; }
        Nd u = dn.l;
        if(u.r==du) {
            u.r=dn.r;
            u.h=Max(u.l.h,u.r.h)+1;
            u.c=u.l.c+u.r.c+1;
            return u;
        }
        u=Fd3(u,dn);
        if(Abs(dn.l.l.h-dn.l.r.h)>1) { u.l=Rotate(dn.l); }
        else {
            dn.l.h=Max(dn.l.l.h,dn.l.r.h)+1;
            dn.l.c=dn.l.l.c+dn.l.r.c+1;
        }
        u.h=Max(u.l.h,u.r.h)+1;
        u.c=u.l.c+u.r.c+1;
        return u;
    }
    private Nd Fd3(Nd u,Nd dn) {
        if(u.r.r!=du) {
            Nd v = Fd3(u.r,dn);
            if(Abs(u.r.l.h-u.r.r.h)>1) { u.r=Rotate(u.r); }
            else {
                u.r.h=Max(u.r.l.h,u.r.r.h)+1;
                u.r.c=u.r.l.c+u.r.r.c+1;
            }
            return v;
        }
        else {
            Nd v = u.r; u.r=u.r.l; v.l=dn.l; v.r=dn.r;
            return v;
        }
    }
    public bool Hs(nint n) {
        Nd t = root;
        if(cnt==0) { return false; }
        if(t.n==n) { return true; }
        bool bo = false;
        while(true) {
            if(t.n>n) {
                if(t.l==du) { break; }
                else if(t.l.n!=n) { t=t.l; }
                else { bo=true; break; }
            }
            else {
                if(t.r==du) { break; }
                else if(t.r.n!=n) { t=t.r; }
                else { bo=true; break; }
            }
        }
        return bo;
    }
    public Nd Ra(int n) { return cnt>=n&&cnt!=0 ? Fr(root,n) : null; }
    private Nd Fr(Nd t,int n) {
        if(t.l.c>n-1) { return Fr(t.l,n); }
        if(t.l.c<n-1) { return Fr(t.r,n-t.l.c-1); }
        return t;
    }
    public Nd Lb(nint n) { return cnt!=0 ? Flb(root,n) : null; }
    private Nd Flb(Nd t,nint n) {
        if(t.n<n) {
            if(t.r==du) { return null; }
            return Flb(t.r,n);
        }
        if(t.n>n) {
            if(t.l==du) { return t; }
            Nd u = Flb(t.l,n);
            return u==null ? t : u;
        }
        return t;
    }
    public Nd Ub(nint n) { return cnt!=0 ? Fub(root,n) : null; }
    private Nd Fub(Nd t,nint n) {
        if(t.n>n) {
            if(t.l==du) { return null; }
            return Fub(t.l,n);
        }
        if(t.n<n) {
            if(t.r==du) { return t; }
            Nd u = Fub(t.r,n);
            return u==null ? t : u;
        }
        return t;
    }
    public int Rg(nint a,nint b) { return cnt!=0 ? Frg(root,a,b,false,false) : 0; }
    private int Frg(Nd t,nint a,nint b,bool l,bool r) {
        if(t.h==0) { return 0; }
        if(l&&r) { return t.c; }
        if(t.n<a) { return Frg(t.r,a,b,t.n>=a,r); }
        if(t.n>b) { return Frg(t.l,a,b,l,t.n<=b); }
        return Frg(t.l,a,b,l,t.n<=b)+Frg(t.r,a,b,t.n>=a,r)+1;
    }
    public void En(Action<Nd> f) { if(cnt>0) { Fen(root,f); } }
    private void Fen(Nd t,Action<Nd> f) {
        if(t.l!=du) { Fen(t.l,f); }
        f(t);
        if(t.r!=du) { Fen(t.r,f); }
    }
    public void En(nint l,nint r,Action<Nd> f) { if(cnt>0) { Fen(root,l,r,false,false,f); } }
    private void Fen(Nd t,nint a,nint b,bool l,bool r,Action<Nd> f) {
        if(l&&r) {
            if(t.l!=du) { Fen(t.l,f); }
            f(t);
            if(t.r!=du) { Fen(t.r,f); }
        }
        else {
            if(t.n<a) { if(t.r!=du) { Fen(t.r,a,b,l,r,f); } }
            else if(t.n>b) { if(t.l!=du) { Fen(t.l,a,b,l,r,f); } }
            else {
                if(t.l!=du) { Fen(t.l,a,b,l,t.n<=b,f); }
                f(t);
                if(t.r!=du) { Fen(t.r,a,b,t.n>=a,r,f); }
            }
        }
    }
    public void Enl(nint l,Func<Nd,bool> f) { if(cnt>0) { Fenl(root,l,f); } }
    private bool Fenl(Nd t,nint a,Func<Nd,bool> f) {
        bool bo = true;
        if(t.n<a) {
            if(t.r!=du) { bo&=Fenl(t.r,a,f); }
        }
        else {
            if(t.l!=du) { bo&=Fenl(t.l,a,f); }
            if(bo) { bo&=f(t); }
            if(bo&&t.r!=du) { bo&=Fenl(t.r,a,f); }
        }
        return bo;
    }
    public void Enr(nint r,Func<Nd,bool> f) { if(cnt>0) { Fenr(root,r,f); } }
    private bool Fenr(Nd t,nint b,Func<Nd,bool> f) {
        bool bo = true;
        if(t.n>b) {
            if(t.l!=du) { bo&=Fenr(t.l,b,f); }
        }
        else {
            if(t.r!=du) { bo&=Fenr(t.r,b,f); }
            if(bo) { bo&=f(t); }
            if(bo&&t.l!=du) { bo&=Fenr(t.l,b,f); }
        }
        return bo;
    }
}
public class Pt {
    private StringBuilder sb = new StringBuilder();
    public Pt(Action<Pt> f) { f(this); }
    public void W(int s) { sb.Append(s); }
    public void W(long s) { sb.Append(s); }
    public void W(double s) { sb.Append(s); }
    public void W(decimal s) { sb.Append(s); }
    public void W(char s) { sb.Append(s); }
    public void W(string s) { sb.Append(s); }
    public void W(object s) { sb.Append(s); }
    public void W(params object[] s) { sb.Append(string.Join(" ",s)); }
    public void Wl(int s) { sb.Append(s).AppendLine(); }
    public void Wl(long s) { sb.Append(s).AppendLine(); }
    public void Wl(double s) { sb.Append(s).AppendLine(); }
    public void Wl(decimal s) { sb.Append(s).AppendLine(); }
    public void Wl(char s) { sb.Append(s).AppendLine(); }
    public void Wl(string s) { sb.AppendLine(s); }
    public void Wl(object s) { sb.Append(s).AppendLine(); }
    public void Wl(int[] s) { sb.AppendLine(string.Join(" ",s)); }
    public void Wl(long[] s) { sb.AppendLine(string.Join(" ",s)); }
    public void Wl(double[] s) { sb.AppendLine(string.Join(" ",s)); }
    public void Wl(string[] s) { sb.AppendLine(string.Join(" ",s)); }
    public void Wl(params object[] s) { sb.AppendLine(string.Join(" ",s)); }
    public void Wl() { sb.AppendLine(); }
    public void Sm() { Console.Write(sb); }
    public void Op(StreamWriter sw) {
        sw.Write(sb);
        sw.Close();
    }
    public static bool operator ==(Pt a,Pt b) { return a.sb.ToString()==b.sb.ToString(); }
    public static bool operator !=(Pt a,Pt b) { return a.sb.ToString()!=b.sb.ToString(); }
    public override bool Equals(object obj) { return false; }
    public override int GetHashCode() { return 0; }
}
public class Sc {
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    protected virtual string Rl() { return Console.ReadLine(); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    protected virtual string[] Sp(string st) { return st.Split(); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private T Ct<T>(string s) { return (T)Convert.ChangeType(s,typeof(T)); }
    public virtual int I { get { return int.Parse(Rl()); } }
    public virtual long L { get { return long.Parse(Rl()); } }
    public virtual double D { get { return double.Parse(Rl()); } }
    public virtual string S { get { return Rl(); } }
    public int[] Ia { get { return Array.ConvertAll(Sp(Rl()),int.Parse); } }
    public long[] La { get { return Array.ConvertAll(Sp(Rl()),long.Parse); } }
    public double[] Da { get { return Array.ConvertAll(Sp(Rl()),double.Parse); } }
    public string[] Sa { get { return Sp(Rl()); } }
    public object[] Oa { get { return Sp(Rl()); } }
    public int[] Ia2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse); } }
    public int[] Ia3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),int.Parse); }
    public int[] Ia3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse); }
    public long[] La2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse); } }
    public long[] La3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),long.Parse); }
    public long[] La3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse); }
    public double[] Da2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse); } }
    public double[] Da3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),double.Parse); }
    public T[] Arr<T>(int n,Func<T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(); } return a; }
    public T[] Arr<T>(int n,Func<int,T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i); } return a; }
    public T[] Arr<T>(int n,Func<string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(Sp(Rl())); } return a; }
    public T[] Arr<T>(int n,Func<int,string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i,Sp(Rl())); } return a; }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T, T) Tp2<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1])); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T, T, T) Tp3<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2])); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T, T, T, T) Tp4<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3])); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T, T, T, T, T) Tp5<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4])); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T, T, T, T, T, T) Tp6<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4]), Ct<T>(s[5])); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T1, T2) Tp2<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T2>(s[1])); }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (T1, T1, T2) Tp3<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T1>(s[1]), Ct<T2>(s[2])); }
}
public class Scr:Sc {
    private List<string> li = new List<string>();
    private int l = 0;
    private bool bo = false;
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    protected override string Rl() {
        if(bo) { return li[l++%li.Count]; }
        li.Add(Console.ReadLine());
        return li[li.Count-1];
    }
    public void Again() { bo=true; }
}
public class Sc2:Sc {
    private string[] sps = new string[] { " ","　","\t" };
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    protected override string[] Sp(string st) { return st.Split(sps,StringSplitOptions.RemoveEmptyEntries); }
    public override int I { get { return int.Parse(Sp(Rl())[0]); } }
    public override long L { get { return long.Parse(Sp(Rl())[0]); } }
    public override double D { get { return double.Parse(Sp(Rl())[0]); } }
    public override string S { get { return Sp(Rl())[0]; } }
}
public class Sct:Sc {
    private List<string> li = new List<string>();
    private int l = 0;
    public void Add(int s) { li.Add(s.ToString()); }
    public void Add(long s) { li.Add(s.ToString()); }
    public void Add(double s) { li.Add(s.ToString()); }
    public void Add(string s) { li.Add(s.ToString()); }
    public void Add(object s) { li.Add(s.ToString()); }
    public void Add(int[] s) { li.Add(string.Join(" ",s)); }
    public void Add(long[] s) { li.Add(string.Join(" ",s)); }
    public void Add(double[] s) { li.Add(string.Join(" ",s)); }
    public void Add(string[] s) { li.Add(string.Join(" ",s)); }
    public void Add(object[] s) { li.Add(string.Join(" ",s)); }
    protected override string Rl() { return li[l++]; }
    public void Clear() { li.Clear(); l=0; }
    public void Again() { l=0; }
    public void Pf() { Console.WriteLine(string.Join("\n",li)); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0