結果
問題 | No.5002 stick xor |
ユーザー | kuuso1 |
提出日時 | 2018-05-27 10:38:09 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 941 ms / 1,000 ms |
コード長 | 8,838 bytes |
コンパイル時間 | 33,953 ms |
実行使用メモリ | 1,852 KB |
スコア | 41,575 |
最終ジャッジ日時 | 2018-05-27 10:38:45 |
ジャッジサーバーID (参考情報) |
judge8 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 939 ms
1,852 KB |
testcase_01 | AC | 939 ms
1,852 KB |
testcase_02 | AC | 938 ms
1,852 KB |
testcase_03 | AC | 940 ms
1,852 KB |
testcase_04 | AC | 939 ms
1,844 KB |
testcase_05 | AC | 939 ms
1,844 KB |
testcase_06 | AC | 939 ms
1,788 KB |
testcase_07 | AC | 939 ms
1,852 KB |
testcase_08 | AC | 939 ms
1,852 KB |
testcase_09 | AC | 939 ms
1,848 KB |
testcase_10 | AC | 939 ms
1,844 KB |
testcase_11 | AC | 940 ms
1,852 KB |
testcase_12 | AC | 939 ms
1,852 KB |
testcase_13 | AC | 938 ms
1,840 KB |
testcase_14 | AC | 940 ms
1,852 KB |
testcase_15 | AC | 940 ms
1,852 KB |
testcase_16 | AC | 940 ms
1,796 KB |
testcase_17 | AC | 941 ms
1,848 KB |
testcase_18 | AC | 939 ms
1,796 KB |
testcase_19 | AC | 940 ms
1,848 KB |
testcase_20 | AC | 940 ms
1,852 KB |
testcase_21 | AC | 939 ms
1,792 KB |
testcase_22 | AC | 939 ms
1,852 KB |
testcase_23 | AC | 939 ms
1,852 KB |
testcase_24 | AC | 940 ms
1,844 KB |
testcase_25 | AC | 939 ms
1,848 KB |
testcase_26 | AC | 939 ms
1,840 KB |
testcase_27 | AC | 939 ms
1,844 KB |
testcase_28 | AC | 940 ms
1,844 KB |
testcase_29 | AC | 940 ms
1,844 KB |
testcase_30 | AC | 939 ms
1,852 KB |
testcase_31 | AC | 940 ms
1,844 KB |
ソースコード
#include <iostream> #include <bits/stdc++.h> #include <time.h> #include <sys/timeb.h> #include <cstdio> #include <sys/time.h> 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 = 3200; 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<N;i++){ for(int j=0;j<N;j++){ aa[i][j] = A[i][j]; } } for(int k=0;k<K;k++){ int x = xs[k]; int y = ys[k]; if(ds[k] == 0){ // vertical for(int i=y;i<y+L[k];i++) aa[i][x] ^= 1; } else { // horizontal for(int j=x;j<x+L[k];j++) aa[y][j] ^= 1; } } int sc = 0; for(int i=0;i<N;i++) for(int j=0;j<N;j++) sc += aa[i][j]; sc = N * N - sc; return sc; } int maxSc = (int) -1e9; int maxY[maxK]; int maxX[maxK]; int maxD[maxK]; bool UpdateMax(int ys[], int xs[], int ds[], int sc, bool calc = false){ if(calc) sc = calcScoreNaive(ys, xs, ds); if(sc > maxSc){ //cerr << "update: maxSc:" << maxSc << " -> " << sc << " : " << Now() <<" [ms]" << endl; maxSc = sc; for(int i=0;i<K;i++){ maxY[i] = ys[i]; maxX[i] = xs[i]; maxD[i] = ds[i]; } return true; } return false; } void Greedy1(){ vector<pair<int, int>> ls(K); for(int i=0;i<K;i++){ ls[i] = make_pair(-L[i], i); } sort(ls.begin(), ls.end()); int a[maxN][maxN]; for(int i=0;i<N;i++){ for(int j=0;j<N;j++) a[i][j] = A[i][j]; } int xs[maxK]; int ys[maxK]; int ds[maxK]; Acc2 sum2; for(int k=0;k<K;k++){ int l = ls[k].first * -1; sum2.Init(a, N, N); int y = -1, x = -1, vh = -1; int max = -1; for(int i=0;i+l <= N;i++){ for(int j=0;j<N;j++){ int s = sum2.Calc(j, i, j + 1, i + l); if(s > max){ max = s; x = j; y = i; vh = 0; } } } for(int i=0;i<N;i++){ for(int j=0;j+l<=N;j++){ int s = sum2.Calc(j, i, j + l, i + 1); if(s > 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<y+l;i++) a[i][x] ^= 1; } else { for(int j=x;j<x+l;j++) a[y][j] ^= 1; } } UpdateMax(ys, xs, ds, 0, true); } void SA(ll tlimit){ int a[maxN][maxN]; int xs[maxK]; int ys[maxK]; int ds[maxK]; ll tstart = Now(); ll timeLimitDuration = tlimit - tstart; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ a[i][j] = A[i][j]; } } Xor128 rnd(25252525); for(int i=0;i<K;i++){ xs[i] = rnd.Next(N - L[i] + 1); ys[i] = rnd.Next(N - L[i] + 1); ds[i] = rnd.Next(2); } for(int k=0;k<K;k++){ int x = xs[k]; int y = ys[k]; if(ds[k] == 0){ // vertical for(int i=y;i<y+L[k];i++) a[i][x] ^= 1; } else { // horizontal for(int j=x;j<x+L[k];j++) a[y][j] ^= 1; } } int sc = calcScoreNaive(ys, xs, ds); UpdateMax(ys, xs, ds, sc); ll cnt = 0; ll t1 = Now(); while(true){ cnt++; if(cnt % 16384 == 0 && (t1 = Now()) - tstart > 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<y+L[pos];i++) one += a[i][x]; } else { // horizontal for(int j=x;j<x+L[pos];j++) one += a[y][j]; } if(ds[pos] == 0){ // vertical for(int i=ys[pos];i<ys[pos]+L[pos];i++) one += a[i][xs[pos]]; } else { // horizontal for(int j=xs[pos];j<xs[pos]+L[pos];j++) one += a[ys[pos]][j]; } int tot = 2 * L[pos]; //Err("y:{0}, x:{1}, vh: {2}, ys[pos]:{3}, xs[pos]:{4}, ds[pos]:{5}, L[pos]:{6}",y, x, vh, ys[pos], xs[pos], ds[pos], L[pos]); if(vh == 0 && ds[pos] == 0){ if(x == xs[pos]){ if(y <= ys[pos] && ys[pos] <= y + L[pos] - 1){ for(int i=ys[pos]; i <= y + L[pos] - 1; i++){ one -= 2 * a[i][x]; tot -= 2; } } else if(ys[pos] <= y && y <= ys[pos] + L[pos] - 1){ for(int i=y; i <= ys[pos] + L[pos] - 1; i++){ one -= 2 * a[i][x]; tot -= 2; } } } } if(vh == 1 && ds[pos] == 1){ if(y == ys[pos]){ if(x <= xs[pos] && xs[pos] <= x + L[pos] - 1){ for(int j=xs[pos]; j <= x + L[pos] - 1; j++){ one -= 2 * a[y][j]; tot -= 2; } } else if(xs[pos] <= x && x <= xs[pos] + L[pos] - 1){ for(int j=x; j <= xs[pos] + L[pos] - 1; j++){ one -= 2 * a[y][j]; tot -= 2; } } } } if(vh == 0 && ds[pos] == 1){ if(InRange(x, xs[pos], xs[pos] + L[pos]) && InRange(ys[pos], y, y + L[pos])){ one -= 2 * a[ys[pos]][x]; tot -= 2; } } if(vh == 1 && ds[pos] == 0){ if(InRange(xs[pos], x, x + L[pos]) && InRange(y, ys[pos], ys[pos] + L[pos])){ one -= 2 * a[y][xs[pos]]; tot -= 2; } } zero = tot - one; int nsc = sc + (one - zero); if(SAgain(nsc, sc, t1, tstart, timeLimitDuration)){ if(vh == 0){ // vertical for(int i=y;i<y+L[pos];i++) a[i][x] ^= 1; } else { // horizontal for(int j=x;j<x+L[pos];j++) a[y][j] ^= 1; } if(ds[pos] == 0){ // vertical for(int i=ys[pos];i<ys[pos]+L[pos];i++) a[i][xs[pos]] ^= 1; } else { // horizontal for(int j=xs[pos];j<xs[pos]+L[pos];j++) a[ys[pos]][j] ^= 1; } sc = nsc; xs[pos] = x; ys[pos] = y; ds[pos] = vh; UpdateMax(ys, xs, ds, sc); } else { } } //Err("cnt: {0}", cnt); //cerr << cnt << endl; } void Solve(){ Greedy1(); SA(900); for(int i=0;i<K;i++){ if(maxD[i] == 0){ printf("%d %d %d %d\n", maxY[i] + 1, maxX[i] + 1, maxY[i] + 1 + L[i] - 1, maxX[i] + 1); } else { printf("%d %d %d %d\n", maxY[i] + 1, maxX[i] + 1, maxY[i] + 1, maxX[i] + 1 + L[i] - 1); } } } int main(){ T.Start(); cin >> N >> K; for(int i=0;i<K;i++){ cin >> L[i]; } string s; for(int i=0;i<N;i++){ cin >> s; for(int j=0;j<N;j++){ A[i][j] = (int) (s[j] - '0'); } } Solve(); return 0; }