{"id":192,"date":"2012-04-24T04:38:00","date_gmt":"2012-04-23T20:38:00","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=192"},"modified":"2012-04-24T17:04:32","modified_gmt":"2012-04-24T09:04:32","slug":"srm-481","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-481\/","title":{"rendered":"SRM 481"},"content":{"rendered":"

Brief description: <\/h3>\n

DIV 1 1000 XorLife\uff1a
\n\u7fa4\u4f17\u559c\u95fb\u4e50\u89c1\u7684\u751f\u547d\u6e38\u620f\uff0c\u5982\u6807\u9898\u5b57\u9762\u4e0a\u7684\u610f\u601d\uff0c\u6bcf\u4e00\u4e2a Live \u683c\u5b50\u4e0b\u4e00\u79d2\u5c06\u6539\u53d8\u5176\u81ea\u8eab\u548c\u5468\u56f4\u5171 5 \u4e2a\u683c\u5b50\u7684\u72b6\u6001\u3002
\n\uff08\u3002\u3002\u65e0\u9650\u5e73\u9762\uff0c\u521d\u59cb\u57f9\u517b\u76bf\u5927\u5c0f 50 \u00d7 50 … \u65f6\u95f4 K \u2264 1,000,000,000 ..\uff09<\/p>\n

<\/p>\n

Analysis: <\/h3>\n
\r\n\/* &*#()&*#)&E*F& *\/\r\n\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <ctime>\r\n#include <cmath>\r\n#include <algorithm>\r\n#include <sstream>\r\n#include <string>\r\n#include <vector>\r\n#include <map>\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i<int(n);++i)\r\n#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)\r\n#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)\r\n#define REP_1(i, n) for (int i=1;i<=int(n);++i)\r\n#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)\r\n#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)\r\n#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)\r\n#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)\r\n#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)\r\n#define REP_N(i, n) for (i=0;i<int(n);++i)\r\n#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)\r\n#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)\r\n#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)\r\n#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)\r\n#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)\r\n#define REP_1_N(i, n) for (i=1;i<=int(n);++i)\r\n#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)\r\n#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)\r\n#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)\r\n#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)\r\n#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)\r\n#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)\r\n#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)\r\n#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)\r\n\r\n#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)\r\n#define DO(n) while(n--)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\n#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)\r\n#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)\r\n#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j)\r\n#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j)\r\n#define REP_2(i, j, n, m) REP(i, n) REP(j, m)\r\n#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)\r\n\r\n#define ALL(A) A.begin(), A.end()\r\n#define CLR(A) A.clear()\r\n#define CPY(A, B) memcpy(A, B, sizeof(A))\r\n#define INS(A, P, B) A.insert(A.begin() + P, B)\r\n#define ERS(A, P) A.erase(A.begin() + P)\r\n#define SRT(A) sort(ALL(A))\r\n#define SZ(A) int(A.size())\r\n#define PB push_back\r\n#define MP(A, B) make_pair(A, B)\r\n\r\ntypedef long long LL;\r\ntypedef double DB;\r\n\r\ntemplate<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}\r\ntemplate<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}\r\n\r\n\/\/ <<= ` 0. Daily Use .,\r\n\r\ntemplate<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}\r\ntemplate<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}\r\ntemplate <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}\r\ntemplate <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}\r\ntemplate<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}\r\ntemplate<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}\r\ntemplate<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}\r\ntemplate<class T> inline T sqr(T a){return a*a;}\r\ntemplate<class T> inline T cub(T a){return a*a*a;}\r\nint Ceil(int x, int y){return (x - 1) \/ y + 1;}\r\n\r\n\/\/ <<= ` 1. Bitwise Operation .,\r\n\r\ninline bool _1(int x, int i){return x & 1<<i;}\r\ninline int _1(int i){return 1<<i;}\r\ninline int _U(int i){return _1(i) - 1;};\r\n\r\ninline int count_bits(int x){\r\n    x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);\r\n    x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);\r\n    x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);\r\n    x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);\r\n    x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);\r\n    return x;\r\n}\r\n\r\ntemplate<class T> inline T low_bit(T x) {\r\n    return x & -x;\r\n}\r\n\r\ntemplate<class T> inline T high_bit(T x) {\r\n    T p = low_bit(x);\r\n    while (p != x) x -= p, p = low_bit(x);\r\n    return p;\r\n}\r\n\r\n\r\n\r\n\/* -&$&#*( &#*@)^$@&*)*\/\r\n\r\nconst int MOD = 1000000007;\r\nconst int INF = 0x7fffffff;\r\n\r\nconst int N = 50;\r\n\r\nint dx[] = {0, 0, 0, 1, -1};\r\nint dy[] = {0, 1, -1, 0, 0};\r\n\r\nmap<pair<int, int>, int> P, Q, _Q;\r\n\r\nmap<pair<int, int>, int> dir[39], tmp;\r\n\r\nvoid Collision(map<pair<int, int>, int>& A){\r\n    for (map<pair<int, int>, int>::iterator it=A.begin(); it!=A.end();){\r\n        if (!(it->second &1)){\r\n            map<pair<int, int>, int>::iterator jt = it; ++jt;\r\n            A.erase(it); it = jt;\r\n        }\r\n        else {\r\n            ++it;\r\n        }\r\n    }\r\n}\r\n\r\n\r\nclass XorLife {\r\npublic:\r\n\tlong long countAliveCells(vector <string> field, int K) {\r\n\r\n        int n = SZ(field), m = SZ(field[0]); REP(i, 32) CLR(dir[i]);\r\n        dir[0][MP(0, 0)] = 1, dir[0][MP(1, 0)] = 1, dir[0][MP(-1, 0)] = 1;\r\n        dir[0][MP(0, 1)] = 1, dir[0][MP(0, -1)] = 1;\r\n\r\n        FOR(i, 1, 32){\r\n            tmp = dir[i-1]; ECH(it, tmp){\r\n                int x = it->first.first, y = it->first.second;\r\n                ECH(jt, dir[i-1]){\r\n                    int xx = x + jt->first.first, yy = y + jt->first.second;\r\n                    ++dir[i][MP(xx, yy)];\r\n                }\r\n            }\r\n\r\n            ECH(it, dir[i]) if (!(it->second&1)) dir[i].erase(it);\r\n        }\r\n\r\n\r\n        CLR(Q); REP(i, n) REP(j, m) if (field[i][j] == 'o'){\r\n            ++Q[MP(i, j)];\r\n        }\r\n\r\n        if (Q.empty()) return 0;\r\n\r\n        int i; FOR_N(i, 0, 32) if (_1(K, i)){\r\n\r\n            cout << i << endl;\r\n\r\n            CLR(P); ECH(it, Q){\r\n                int x = it->first.first, y = it->first.second;\r\n                ECH(jt, dir[i]){\r\n                    int xx = x + jt->first.first, yy = y + jt->first.second;\r\n                    ++P[MP(xx, yy)];\r\n                }\r\n            }\r\n\r\n            Collision(P), Q = P;\r\n        }\r\n        else {\r\n            if (i > 8) break;\r\n        }\r\n\r\n        LL res = SZ(Q); CLR(Q); ++Q[MP(0, 0)];\r\n        FOR_N(i, i+1, 32) if (_1(K, i)){\r\n           CLR(P); ECH(it, Q){\r\n                int x = it->first.first, y = it->first.second;\r\n                ECH(jt, dir[i]){\r\n                    int xx = x + jt->first.first, yy = y + jt->first.second;\r\n                    ++P[MP(xx, yy)];\r\n                }\r\n            }\r\n\r\n            Collision(P), Q = P;\r\n        }\r\n        else {\r\n            res *= SZ(Q);\r\n            CLR(Q); ++Q[MP(0, 0)];\r\n        }\r\n\r\n        return res;\r\n\t}\r\n};\r\n\r\n\r\n\/\/ BEGIN CUT HERE\r\nnamespace moj_harness {\r\n\tint run_test_case(int);\r\n\tvoid run_test(int casenum = -1, bool quiet = false) {\r\n\t\tif (casenum != -1) {\r\n\t\t\tif (run_test_case(casenum) == -1 && !quiet) {\r\n\t\t\t\tcerr << "Illegal input! Test case " << casenum << " does not exist." << endl;\r\n\t\t\t}\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tint correct = 0, total = 0;\r\n\t\tfor (int i=0;; ++i) {\r\n\t\t\tint x = run_test_case(i);\r\n\t\t\tif (x == -1) {\r\n\t\t\t\tif (i >= 100) break;\r\n\t\t\t\tcontinue;\r\n\t\t\t}\r\n\t\t\tcorrect += x;\r\n\t\t\t++total;\r\n\t\t}\r\n\r\n\t\tif (total == 0) {\r\n\t\t\tcerr << "No test cases run." << endl;\r\n\t\t} else if (correct < total) {\r\n\t\t\tcerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;\r\n\t\t} else {\r\n\t\t\tcerr << "All " << total << " tests passed!" << endl;\r\n\t\t}\r\n\t}\r\n\r\n\tint verify_case(int casenum, const long long &expected, const long long &received, clock_t elapsed) {\r\n\t\tcerr << "Example " << casenum << "... ";\r\n\r\n\t\tstring verdict;\r\n\t\tvector<string> info;\r\n\t\tchar buf[100];\r\n\r\n\t\tif (elapsed > CLOCKS_PER_SEC \/ 200) {\r\n\t\t\tsprintf(buf, "time %.2fs", elapsed * (1.0\/CLOCKS_PER_SEC));\r\n\t\t\tinfo.push_back(buf);\r\n\t\t}\r\n\r\n\t\tif (expected == received) {\r\n\t\t\tverdict = "PASSED";\r\n\t\t} else {\r\n\t\t\tverdict = "FAILED";\r\n\t\t}\r\n\r\n\t\tcerr << verdict;\r\n\t\tif (!info.empty()) {\r\n\t\t\tcerr << " (";\r\n\t\t\tfor (int i=0; i<(int)info.size(); ++i) {\r\n\t\t\t\tif (i > 0) cerr << ", ";\r\n\t\t\t\tcerr << info[i];\r\n\t\t\t}\r\n\t\t\tcerr << ")";\r\n\t\t}\r\n\t\tcerr << endl;\r\n\r\n\t\tif (verdict == "FAILED") {\r\n\t\t\tcerr << "    Expected: " << expected << endl;\r\n\t\t\tcerr << "    Received: " << received << endl;\r\n\t\t}\r\n\r\n\t\treturn verdict == "PASSED";\r\n\t}\r\n\r\n\tint run_test_case(int casenum) {\r\n\t\tswitch (casenum) {\r\n\t\tcase 0: {\r\n\t\t\tstring field[]            = {".", ".", ".", ".", ".", "o", ".", "o", ".", "o", ".", "o", ".", ".", ".", ".", ".", ".", "o", "o", ".", ".", ".", ".", "o", ".", ".", "o", ".", ".", "o", ".", ".", ".", "o", ".", ".", ".", "o", "o", ".", ".", "o", ".", ".", ".", ".", ".", "o", "."};\r\n\t\t\tint K                     = 8095;\r\n\t\t\tlong long expected__      = 6199756;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}\r\n\t\tcase 1: {\r\n\t\t\tstring field[]            = {".."\r\n,".."};\r\n\t\t\tint K                     = 23;\r\n\t\t\tlong long expected__      = 0;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}\r\n\t\tcase 2: {\r\n\t\t\tstring field[]            = {"o"};\r\n\t\t\tint K                     = 1234567;\r\n\t\t\tlong long expected__      = 11018125;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}\r\n\t\tcase 3: {\r\n\t\t\tstring field[]            = {"o.oo.ooo"\r\n,"o.o.o.oo"\r\n,"ooo.oooo"\r\n,"o.o..o.o"\r\n,"o.o..o.o"\r\n,"o..oooo."\r\n,"..o.o.oo"\r\n,"oo.ooo.o"};\r\n\t\t\tint K                     = (1<<31)-1;\r\n\t\t\tlong long expected__      = 447104494375LL;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}\r\n\r\n\t\t\/\/ custom cases\r\n\r\n\/*      case 4: {\r\n\t\t\tstring field[]            = ;\r\n\t\t\tint K                     = ;\r\n\t\t\tlong long expected__      = ;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}*\/\r\n\/*      case 5: {\r\n\t\t\tstring field[]            = ;\r\n\t\t\tint K                     = ;\r\n\t\t\tlong long expected__      = ;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}*\/\r\n\/*      case 6: {\r\n\t\t\tstring field[]            = ;\r\n\t\t\tint K                     = ;\r\n\t\t\tlong long expected__      = ;\r\n\r\n\t\t\tclock_t start__           = clock();\r\n\t\t\tlong long received__      = XorLife().countAliveCells(vector <string>(field, field + (sizeof field \/ sizeof field[0])), K);\r\n\t\t\treturn verify_case(casenum, expected__, received__, clock()-start__);\r\n\t\t}*\/\r\n\t\tdefault:\r\n\t\t\treturn -1;\r\n\t\t}\r\n\t}\r\n}\r\n\r\nint main(int argc, char *argv[]) {\r\n\tif (argc == 1) {\r\n\t\tmoj_harness::run_test();\r\n\t} else {\r\n\t\tfor (int i=1; i<argc; ++i)\r\n\t\t\tmoj_harness::run_test(atoi(argv[i]));\r\n\t}\r\n}\r\n\/\/ END CUT HERE\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Brief description: DIV 1 1000 XorLife\uff1a \u7fa4\u4f17\u559c\u95fb\u4e50\u89c1\u7684\u751f\u547d\u6e38\u620f\uff0c\u5982\u6807\u9898\u5b57\u9762\u4e0a\u7684\u610f\u601d\uff0c\u6bcf\u4e00\u4e2a Live \u683c\u5b50\u4e0b\u4e00\u79d2\u5c06\u6539\u53d8\u5176\u81ea\u8eab\u548c\u5468\u56f4\u5171 5 \u4e2a\u683c\u5b50\u7684\u72b6\u6001\u3002 \uff08\u3002\u3002\u65e0\u9650\u5e73\u9762\uff0c\u521d\u59cb\u57f9\u517b\u76bf\u5927\u5c0f 50 \u00d7 50 … \u65f6\u95f4 K \u2264 1,000,000,000 ..\uff09<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-192","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-36","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/192","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=192"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/192\/revisions"}],"predecessor-version":[{"id":193,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/192\/revisions\/193"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=192"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=192"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=192"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}