#include #include #include #include #include #include using namespace std; #define ll long long #define uint unsigned int #define ulong unsigned long long int #define maxN 200 #define maxK 600 int N, K; int L[maxK]; int A[maxN][maxN]; int H, W; class Acc2{ public: int H,W; int acc[maxN][maxN]; int Calc(int x1,int y1,int x2,int y2){ //return num of land [x1,x2)*[y1,y2); left-inclusive / right-noninclusive; if(x2 < x1 || y2 < y1) return 0; return acc[y2][x2] - acc[y2][x1] - acc[y1][x2] + acc[y1][x1]; } Acc2(int a[maxN][maxN], int h, int w){ Init(a, h, w); } Acc2(){ } void Init(int M[maxN][maxN], int h, int w){ H = h; W = w; for(int i=0;i<=H;i++){ for(int j=0;j<=W;j++){ acc[i][j] = (i == 0 || j == 0) ? 0 : M[i-1][j-1]; } } for(int i=1;i<=H;i++){ for(int j=1;j<=W;j++){ acc[i][j] += acc[i][j-1]; } } for(int j=1;j<=W;j++){ for(int i=1;i<=H;i++){ acc[i][j] += acc[i-1][j]; } } } }; class Xor128{ private: uint x, y, z, w; public: void init(uint seed = 0){ x = 123456789; y = 362436069; z = 521288629; w = 88675123; z ^= seed; } Xor128(){init();} Xor128(uint seed){init(seed);} inline uint Next(){ uint t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } inline int Next(int ul){ return ul == 0 ? 0 : NextI(0,ul-1); } inline int NextI(int from,int to){ int mod=to-from+1; int ret=(int)(Next()%mod); return ret+from; } inline double NextD(){ return (Next() & 1048575) / 1048575.0; } }; class Timer{ public: Timer(){ cycle_per_sec = (ulong) 2.7e9; } void Start(){ begin_cycle = getCycle(); } double getTime(){ return (double)(getCycle() - begin_cycle) / cycle_per_sec; } int elapsedMilliseconds(){ return (int)( 1000 * getTime() ); } ulong getCycle(){ uint low, high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((ulong) low) | ((ulong) high << 32); } private: ulong begin_cycle; ulong cycle_per_sec; }; Timer T; ll Now(){return (ll) T.elapsedMilliseconds();} const int MD = 10; const int MASK = 0x3FF; inline int decR(int s){return s >> MD;} inline int decC(int s){return s & MASK;} inline int enc(int r,int c){return (r << MD) + c;} int dy[]{0, 1, 1, 1, 0, -1, -1, -1, 0,-2, 0,2}; int dx[]{1, 1, 0,-1, -1, -1, 0, 1, 2, 0,-2,0}; const double Inf = 1e18; const double Eps = 1e-9; bool InRange(int t, int l, int r){ return l <= t && t < r;} void Swap(int &a, int &b){ int t = a; a = b; b = t;} void Init(){ } // SA template Xor128 lottery(25252525); const double C = 2400; const double invLimitDuration = 1 / 900.0; inline bool SAgain(double score, double prev, long now, long start, long limitDuration){ if( score > prev ) return true; double ratio = - (prev - score) / prev; double remainingTime = (now - start) * invLimitDuration; if( remainingTime > 1.0) return false; remainingTime = 1 - remainingTime; double acProb = exp(C * ratio / remainingTime); return (lottery.NextD() + Eps) < acProb ; } bool MCgain(double score, double prev, long now, long start, long limitDuration){ if( score > prev ) return true; return false; } int calcScoreNaive(int ys[], int xs[], int ds[]){ int aa[maxN][maxN]; for(int i=0;i maxSc){ //cerr << "update: maxSc:" << maxSc << " -> " << sc << " : " << Now() <<" [ms]" << endl; maxSc = sc; for(int i=0;i> ls(K); for(int i=0;i max){ max = s; x = j; y = i; vh = 0; } } } for(int i=0;i max){ max = s; x = j; y = i; vh = 1; } } } int idx = ls[k].second; xs[idx] = x; ys[idx] = y; ds[idx] = vh; if(vh == 0){ for(int i=y;i timeLimitDuration) break; int vh = rnd.Next(2); int pos = rnd.Next(K); int y = rnd.Next(vh == 0 ? N - L[pos] + 1 : N); int x = rnd.Next(vh == 1 ? N - L[pos] + 1 : N); int one = 0; int zero = 0; if(vh == 0){ // vertical for(int i=y;i> N >> K; for(int i=0;i> L[i]; } string s; for(int i=0;i> s; for(int j=0;j