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
