結果
| 問題 | No.130 XOR Minimax |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-07-27 15:59:00 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,065 bytes |
| コンパイル時間 | 2,394 ms |
| コンパイル使用メモリ | 114,292 KB |
| 実行使用メモリ | 165,580 KB |
| 最終ジャッジ日時 | 2024-09-12 23:00:48 |
| 合計ジャッジ時間 | 50,701 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 WA * 1 |
コンパイルメッセージ
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.Collections;using System.Collections.Specialized;using System.Linq;using System.Text;using System.IO;using System.Reflection;using static System.Math;using System.Numerics;static class Program{const int mod=(int)1e9+7;const double eps=1e-11;static void Main(){Sc sc=new Sc();var n=sc.I;DateTime st=DateTime.Now;var a=sc.Ia;var bt=new Bt();for(int i = 0;i<n;i++) {bt.Add(a[i]);}int x=0,m=a.Max();long p=bt.Ra(n),ans=p;const int t=1892;Random r=new Random(1);var dd=(DateTime.Now-st).TotalMilliseconds;while(dd<1900){var tp=t-dd;for(int i = 0;1<<i<=m;i++) {var g=bt.Ra(n,x^(1<<i));if(p>g||r.Next(1000000000)<Exp((p-g)/tp)*1000000000){p=g;x^=1<<i;ans=Min(ans,p);}}dd=(DateTime.Now-st).TotalMilliseconds;}Console.WriteLine("{0}",ans);}}public class Bt{private const int b=30;private Nd r;public class Nd{public int d;public long n;public Nd[] h=new Nd[2];public override string ToString()=>"n:"+n.ToString()+" d:"+d.ToString();}public Bt(){r=new Nd();}public void Add(long n){var t=r;t.d++;for(int i = b;i>=0;i--) {long k=(n>>i)&1;t=t.h[k]==null?t.h[k]=new Nd():t.h[k];t.d++;}t.n=n;}public void Dl(long n){var t=r;t.d--;for(int i = b;i>=0;i--) {t=t.h[(n>>i)&1];t.d--;}}public long Ra(int n){if(n>r.d||n<1){return -1;}var t=r;for(int i = b;i>=0;i--) {if(t.h[0]==null){t=t.h[1];}else if(t.h[0].d<n){n-=t.h[0].d;t=t.h[1];}else{t=t.h[0];}}return t.n;}public long Ra(int n,int x){if(n>r.d||n<1){return -1;}var t=r;for(int i = b;i>=0;i--) {int k=(x>>i)&1;if(t.h[k]==null){t=t.h[k^1];}else if(t.h[k].d<n){n-=t.h[k].d;t=t.h[k^1];}else{t=t.h[k];}}return t.n^x;}public long Lb(long n){return Flb(r,n,b,1);}private long Flb(Nd t,long n,int b,int o){if(b==-1){return t.d!=0?t.n:-1;}int k=(int)((n>>b)&o);if(t.h[k]!=null&&t.h[k].d!=0){var p=Flb(t.h[k],n,b-1,o);if(p!=-1){return p;}}if(k==0&&t.h[1]!=null&&t.h[1].d!=0){return Flb(t.h[1],n,b-1,0);}return -1;}public long Ub(long n){return Fub(r,n,b,0);}private long Fub(Nd t,long n,int b,int o){if(b==-1){return t.d!=0?t.n:-1;}int k=((int)((n>>b)&1))|o;if(t.h[k]!=null&&t.h[k].d!=0){var p=Fub(t.h[k],n,b-1,o);if(p!=-1){return p;}}if(k==1&&t.h[0]!=null&&t.h[0].d!=0){return Fub(t.h[0],n,b-1,1);}return -1;}public long Max(){var t=r;for(int i = b;i>=0;i--) {t=t.h[1]!=null&&t.h[1].d!=0?t.h[1]:t.h[0];}return t.n;}public long Min(){var t=r;for(int i = b;i>=0;i--) {t=t.h[0]!=null&&t.h[0].d!=0?t.h[0]:t.h[1];}return t.n;}public long Max(long x){var t=r;for(int i = b;i>=0;i--) {int k=(int)(((x>>i)^1)&1);t=t.h[k]!=null&&t.h[k].d!=0?t.h[k]:t.h[k^1];}return t.n^x;}public long Min(long x){var t=r;for(int i = b;i>=0;i--) {int k=(int)(((x>>i)^1)&1)^1;t=t.h[k]!=null&&t.h[k].d!=0?t.h[k]:t.h[k^1];}return t.n^x;}public int cnt{get{return r.d;}}}public class Sc{public int I{get{return int.Parse(Console.ReadLine());}}public long L{get{return long.Parse(Console.ReadLine());}}public double D{get{return double.Parse(Console.ReadLine());}}public string S{get{return Console.ReadLine();}}public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}public string[] Sa{get{return Console.ReadLine().Split();}}public object[] Oa{get{return Console.ReadLine().Split();}}public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}public int[] Ia3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);}public int[] Ia3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),int.Parse);}public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);}public long[] La3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),long.Parse);}public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),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(Console.ReadLine().Split());}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,Console.ReadLine().Split());}return a;}}