某島

… : "…アッカリ~ン . .. . " .. .
April 24, 2012

SRM 481

Brief description:

DIV 1 1000 XorLife:
群眾喜聞樂見的生命遊戲,如標題字面上的意思,每一個 Live 格子下一秒將改變其自身和周圍共 5 個格子的狀態。
(。。無限平面,初始培養皿大小 50 × 50 … 時間 K ≤ 1,000,000,000 ..)

Analysis:

/* &*#()&*#)&E*F& */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)

#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)
#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)
#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)
#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j)
#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j)
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

// <<= ` 0. Daily Use .,

template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
int Ceil(int x, int y){return (x - 1) / y + 1;}

// <<= ` 1. Bitwise Operation .,

inline bool _1(int x, int i){return x & 1<<i;}
inline int _1(int i){return 1<<i;}
inline int _U(int i){return _1(i) - 1;};

inline int count_bits(int x){
    x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
    x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
    x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
    x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
    x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
    return x;
}

template<class T> inline T low_bit(T x) {
    return x & -x;
}

template<class T> inline T high_bit(T x) {
    T p = low_bit(x);
    while (p != x) x -= p, p = low_bit(x);
    return p;
}



/* -&$&#*( &#*@)^$@&*)*/

const int MOD = 1000000007;
const int INF = 0x7fffffff;

const int N = 50;

int dx[] = {0, 0, 0, 1, -1};
int dy[] = {0, 1, -1, 0, 0};

map<pair<int, int>, int> P, Q, _Q;

map<pair<int, int>, int> dir[39], tmp;

void Collision(map<pair<int, int>, int>& A){
    for (map<pair<int, int>, int>::iterator it=A.begin(); it!=A.end();){
        if (!(it->second &1)){
            map<pair<int, int>, int>::iterator jt = it; ++jt;
            A.erase(it); it = jt;
        }
        else {
            ++it;
        }
    }
}


class XorLife {
public:
	long long countAliveCells(vector <string> field, int K) {

        int n = SZ(field), m = SZ(field[0]); REP(i, 32) CLR(dir[i]);
        dir[0][MP(0, 0)] = 1, dir[0][MP(1, 0)] = 1, dir[0][MP(-1, 0)] = 1;
        dir[0][MP(0, 1)] = 1, dir[0][MP(0, -1)] = 1;

        FOR(i, 1, 32){
            tmp = dir[i-1]; ECH(it, tmp){
                int x = it->first.first, y = it->first.second;
                ECH(jt, dir[i-1]){
                    int xx = x + jt->first.first, yy = y + jt->first.second;
                    ++dir[i][MP(xx, yy)];
                }
            }

            ECH(it, dir[i]) if (!(it->second&1)) dir[i].erase(it);
        }


        CLR(Q); REP(i, n) REP(j, m) if (field[i][j] == 'o'){
            ++Q[MP(i, j)];
        }

        if (Q.empty()) return 0;

        int i; FOR_N(i, 0, 32) if (_1(K, i)){

            cout << i << endl;

            CLR(P); ECH(it, Q){
                int x = it->first.first, y = it->first.second;
                ECH(jt, dir[i]){
                    int xx = x + jt->first.first, yy = y + jt->first.second;
                    ++P[MP(xx, yy)];
                }
            }

            Collision(P), Q = P;
        }
        else {
            if (i > 8) break;
        }

        LL res = SZ(Q); CLR(Q); ++Q[MP(0, 0)];
        FOR_N(i, i+1, 32) if (_1(K, i)){
           CLR(P); ECH(it, Q){
                int x = it->first.first, y = it->first.second;
                ECH(jt, dir[i]){
                    int xx = x + jt->first.first, yy = y + jt->first.second;
                    ++P[MP(xx, yy)];
                }
            }

            Collision(P), Q = P;
        }
        else {
            res *= SZ(Q);
            CLR(Q); ++Q[MP(0, 0)];
        }

        return res;
	}
};


// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	int verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			string field[]            = {".", ".", ".", ".", ".", "o", ".", "o", ".", "o", ".", "o", ".", ".", ".", ".", ".", ".", "o", "o", ".", ".", ".", ".", "o", ".", ".", "o", ".", ".", "o", ".", ".", ".", "o", ".", ".", ".", "o", "o", ".", ".", "o", ".", ".", ".", ".", ".", "o", "."};
			int K                     = 8095;
			long long expected__      = 6199756;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 1: {
			string field[]            = {".."
,".."};
			int K                     = 23;
			long long expected__      = 0;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 2: {
			string field[]            = {"o"};
			int K                     = 1234567;
			long long expected__      = 11018125;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 3: {
			string field[]            = {"o.oo.ooo"
,"o.o.o.oo"
,"ooo.oooo"
,"o.o..o.o"
,"o.o..o.o"
,"o..oooo."
,"..o.o.oo"
,"oo.ooo.o"};
			int K                     = (1<<31)-1;
			long long expected__      = 447104494375LL;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 4: {
			string field[]            = ;
			int K                     = ;
			long long expected__      = ;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 5: {
			string field[]            = ;
			int K                     = ;
			long long expected__      = ;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 6: {
			string field[]            = ;
			int K                     = ;
			long long expected__      = ;

			clock_t start__           = clock();
			long long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field / sizeof field[0])), K);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE