//#define DEBUG //#undef DEBUG using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Diagnostics; #if DEBUG using System.Threading; #endif public class StickXor{ #region field int N, K; int[][] A; int[] L; #endregion void Solve(){ var d = ria(); N = d[0]; K = d[1]; L = ria(); A = new int[N][]; for(int i=0;i (int)(c - '0')).ToArray(); } SA(900); var sb = new StringBuilder(); for(int i=0;i maxSc){ //Err("update: minSc:{0} -> {1} : {2} [ms]",maxSc, sc, Now()); maxSc = sc; maxY = (int[]) ys.Clone(); maxX = (int[]) xs.Clone(); maxD = (int[]) ds.Clone(); return true; } return false; } void SA(long tlimit){ long tstart = Now(); long timeLimitDuration = tlimit - tstart; int[][] a = new int[N][]; for(int i=0;i timeLimitDuration) break; var vh = rnd.Next(2); var pos = rnd.Next(K); var y = rnd.Next(vh == 0 ? N - L[pos] + 1 : N); var x = rnd.Next(vh == 1 ? N - L[pos] + 1 : N); int gain = 0; if(vh == 0){ // vertical int one = 0; int zero = 0; for(int i=y;i prev ) return true; double ratio = - (prev - score) / prev; double remainingTime = (now - start) / (double) limitDuration; if( remainingTime > 1.0) return false; remainingTime = 1 - remainingTime; double acProb = Math.Exp(C * ratio / remainingTime); return (lottery.NextD() + Eps) < acProb ; } static bool MCgain(double score, double prev, long now, long start, long limitDuration){ if( score > prev ) return true; return false; } static bool SAlose(double score, double prev, long now, long start, long limitDuration){ if( score < prev ) return true; double ratio = (prev - score) / prev; double remainingTime = (now - start) / (double) limitDuration; if( remainingTime > 1.0) return false; remainingTime = 1 - remainingTime; double acProb = Math.Exp(C * ratio / remainingTime); return (lottery.Next(1000000) / 1000000.0 + Eps) < acProb ; } static bool MClose(double score, double prev, long now, long start, long limitDuration){ if( score < prev ) return true; return false; } #endregion #region TimeCount static Stopwatch sw = new Stopwatch(); static bool TU=false; static long TimeLimit=950; static bool TimeUp(){ if(TU){return true;} return TU = (sw.ElapsedMilliseconds>TimeLimit); } static long Now(){return sw.ElapsedMilliseconds;} static bool TUT=false; static long TimeLimitT=3000000; static bool TimeUpT(){ if(TUT){return true;} return TUT=(sw.ElapsedTicks>TimeLimitT); } static long NowT(){return sw.ElapsedTicks;} static void TimeStamp(String title){ Console.Error.WriteLine("{0}:{1} [ms]",title,Now()); } #endregion #region Decode const int MD = 10; const int MASK = 0x2FF; static int decR(int s){return s >> MD;} static int decC(int s){return s & MASK;} static int enc(int r,int c){return (r << MD) + c;} static int[] dy=new int[]{0, -1, 0, 1, 1, -1, -1, 1}; static int[] dx=new int[]{1, 0, -1, 0, 1, 1, -1, -1}; const double Inf = 1e18; const double Eps = 1e-9; static int D2(int x0, int y0, int x1, int y1){ x1 -= x0; y1 -= y0; return x1 * x1 + y1 * y1; } static double D(int x0, int y0, int x1, int y1){ return Math.Sqrt(D2(x0, y0, x1, y1)); } #endregion bool InRange(int t, int l, int r){ return l <= t && t < r;} void Swap (ref T a, ref T b) { T t = a; a = b; b = t;} bool NextPermutation(T[] a)where T:IComparable{ for(int i=a.Length-2;i>=0;i--){ if(a[i].CompareTo(a[i+1])<0){ int trgt=Array.FindLastIndex(a,x=>a[i].CompareTo(x)<0); Swap(ref a[i],ref a[trgt]); Array.Reverse(a,i+1,a.Length-(i+1)); return true; } } Array.Reverse(a); return false; } static void Err(String format, params object[] args){ Console.Error.WriteLine(format, args); } static int seed = 0; public static void Main(){ //seed = int.Parse(args[0]); //C = double.Parse(args[1]); sw.Start(); var sx = new StickXor(); sx.Solve(); } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } #if DEBUG static class DebugClass{ } #endif class Xor128{ uint x = 123456789; uint y = 362436069; uint z = 521288629; uint w = 88675123; const double div = 1.0 / 1048575.0; public Xor128(){ } public Xor128(uint seed){ z ^= seed; } public uint Next(){ uint t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } public int Next(int ul){ return ul == 0 ? 0 : NextI(0,ul-1); } public int NextI(int from,int to){ int mod=to-from+1; int ret=(int)(Next()%mod); return ret+from; } public double NextD(){ return (Next() & 1048575) * div; } }