Skip to content

Instantly share code, notes, and snippets.

@kusano

kusano/SquareRemover.cpp

Created April 23, 2014 17:04
Show Gist options
  • Save kusano/11223722 to your computer and use it in GitHub Desktop.
Save kusano/11223722 to your computer and use it in GitHub Desktop.
Download ZIP
2014 TCO Marathon Round 1 SquareRemover
Raw
SquareRemover.cpp
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <set>
#include <ctime>
#include <algorithm>
using namespace std;
struct Move
{
int pos;
int dir;
Move(){}
Move(int p, int d) : pos(p), dir(d) {}
};
const unsigned long long Hash[6][256] = {
{0xbb5d75b895f628f2LL, 0xd30a286ec6737b8bLL, 0x1bfa530d5d685155LL, 0xa29c4db3d2083355LL, 0xab0a0d83b2ff5134LL, 0x67518339e369ab3dLL, 0xa9eb72624f93de30LL, 0x75ffbff51e5876bfLL, 0xcdd25aa143cd9d75LL, 0x127e2cc80b3bbf03LL, 0xa28f38bd0463522cLL, 0x1ac66dea32700980LL, 0x5074d85b9194e696LL, 0x41dd9a9fa508c8e8LL, 0xb5710cdb11190839LL, 0x311e18c91413b58cLL, 0xe0a9467740c7c159LL, 0x2663ba178df6073dLL, 0x6e10d8ac0af84fd9LL, 0xf8a82a8dbdb78c3fLL, 0xa24898ef0e531c17LL, 0x6164b99c58e8abfcLL, 0xb7a60ec1437f7e5cLL, 0x22d99277310791bbLL, 0x9cf8d97f6451faddLL, 0x40bc08848d85b315LL, 0x5570b28ed7b9ba35LL, 0xb7c8cf3528ba4db2LL, 0x0a14680d52591d5fLL, 0x999613938a3b319fLL, 0x6ffedc96a42ca3e6LL, 0xdfbe3b62670370e8LL, 0xead13c41399fcfd6LL, 0x3c9921edbf0d1338LL, 0xb556ec05d02819d9LL, 0xb1ac56a275f53e2aLL, 0x4674252dee87e8a2LL, 0x4d21b0cb3e36eee3LL, 0xedce70dc54117a0eLL, 0xf82272a99478e208LL, 0x7f0b4c558f78a664LL, 0x26101d6e040e5825LL, 0xfa5035167745f6e1LL, 0x9d823b35bba0cbd5LL, 0x0556d1ddb8c273f1LL, 0x315baf27ca6cff02LL, 0xc0776b023caf3403LL, 0xcc99eb12a1f3ab06LL, 0xac58bc7d67f25bfaLL, 0x50151c6dc099797cLL, 0x6d20bd39b0f2badcLL, 0xa1570f48caceb3ddLL, 0x2b7e9608c8f4cee6LL, 0x31990fffdbdfdb26LL, 0x32648cd6af2b4fdbLL, 0xe97ad106a47bfe3fLL, 0x987c63cf93d56de2LL, 0x6e3dacc90f12121bLL, 0xc9c0c490ae39d9aaLL, 0x12e9831d31b56da5LL, 0x22db2ca5a94de172LL, 0x948e6c1545e4c644LL, 0x3e9a5775f3bf77ecLL, 0x497cff13eaa5bf76LL, 0xeb28e3b1b084410fLL, 0xd9f6bca7d86e01e0LL, 0x7c78397d4ca4cd0eLL, 0x0e7b8cdb9a53727eLL, 0xcaae117ec26c7625LL, 0xc307a9d7d1f78bafLL, 0x65ae497d6bf5f8f7LL, 0x031392cb2c797a45LL, 0x308442bd2f0ab265LL, 0x306743716cd08c92LL, 0x6afaf64c28707959LL, 0xf4e88aad1497184fLL, 0x2fa10751805f567cLL, 0x4e327d5dc1a11dffLL, 0x481191a75247636bLL, 0x53646b1cfee7d9fdLL, 0x37514178b2d9e691LL, 0x89dcdc0ae550eabcLL, 0xf327d42fb261a84dLL, 0xfaa4876465f73e39LL, 0x66244131cd05f916LL, 0xa4de0fa4faf4bf35LL, 0xb89250666f1c7a5eLL, 0xfdf64cc21517c64aLL, 0x369320c5f4d932fdLL, 0xbed86e625cf909dbLL, 0x250b68ac0845024eLL, 0x68a2ad5c9eed7637LL, 0x43ea6daed2a87911LL, 0x56bd43df7bfb015fLL, 0x9e4c13ee5f956c93LL, 0x78e97e8ae0bd6d10LL, 0x7bff8ae147ef37c6LL, 0xbb3f956726b9b05eLL, 0x29c1fcf3b2fefd09LL, 0xa922933b0b315a10LL, 0x1fa7ef6f5a0a0addLL, 0xa81d04c333010b25LL, 0x83e412adbb100261LL, 0x675711b4f3fe1593LL, 0xcfe06e563318e2bcLL, 0xd51ceddab7795459LL, 0xe8ebd27ca97386d0LL, 0xeb7cc914b95b32dfLL, 0x494ee3565122540cLL, 0x412ce7bf0b153a85LL, 0x8934d2f644d07f24LL, 0xe019cf5f08d74c5aLL, 0xd535be69e2b40d48LL, 0x23cbab5def58301dLL, 0xe2f4fc517f35f951LL, 0x0561ef6ea89b3dbfLL, 0x959f4db312dbb5e1LL, 0xbca2014c6234db04LL, 0x20b1eed5978e4900LL, 0xbf037ba260e9c111LL, 0x1384c3552db44714LL, 0x2117120a54ab329aLL, 0x91594a52a4aac9c5LL, 0x8610a613b654b8e1LL, 0x217909c82f899893LL, 0x69b37f5eadafa5f5LL, 0x81181f0b2718bcb6LL, 0xab3d472158d034f1LL, 0x4d8df934efb6fab4LL, 0xb9ecff4f6295b1c5LL, 0x8373759c9fadde3aLL, 0x07d1b965c468048eLL, 0xc61fdb7e3c0218b9LL, 0xb3484b073b479909LL, 0x3f4674f357e7f058LL, 0xb5f50c8d981a4378LL, 0xb6e0dfc356a7b732LL, 0xddeaf197fbd81d07LL, 0x19a73279e90be331LL, 0x6638b2c96c605fa9LL, 0x3bcc47de126dfd0cLL, 0x671dfb202efef734LL, 0x41866137572f48edLL, 0x11d6a9892d43d0f9LL, 0xa3570ab2891296efLL, 0x7038ad525045d6ceLL, 0x866778f238f878c3LL, 0x1c42c81764b11177LL, 0xc40ae2d30ca49e93LL, 0xbaaa128eab882ec7LL, 0x76131ee0ac1b4e27LL, 0xd60cb6c709261387LL, 0xed45d58ed229d3b9LL, 0xf373a091bb9c1ef6LL, 0x936ac7b24c2824b9LL, 0x8a47d84265709634LL, 0x6aad3ec186f7c778LL, 0x253158fe080fbbbfLL, 0x9dd12c9bf84e65fcLL, 0x3ee4f5b5efa08bbeLL, 0x43e081a45e68e47dLL, 0xd8a701c938055370LL, 0x7f07bf881b87c80bLL, 0xa11eb7e11187a4c6LL, 0xebc6e1068f47d489LL, 0x3aedcf06e6c9453aLL, 0xc9839b5b8176772aLL, 0xa6dbe05295731852LL, 0xceee771808fe85e3LL, 0xae08124523897841LL, 0xba95ce9691a616dbLL, 0x0ce9eb4e9f52c1faLL, 0xcabd557ffa1df043LL, 0x754bf882fb6105f5LL, 0x1ada11c5f008a8f2LL, 0x204f7631ab527c0bLL, 0x4052094e68aa8e38LL, 0x4694b80de91b9a59LL, 0xb04e0bb2e91c39feLL, 0x210dceec7505166aLL, 0x47db9e9fbef6db9aLL, 0x50672caa9c72a7c6LL, 0x13c2215bc0d07db3LL, 0x9dcabc0e8c23efcbLL, 0x44f694b7cc483681LL, 0x3de92c0a5593065dLL, 0x8695ed30a3f9cd3aLL, 0xa020a0b2edf1d796LL, 0x68dcdfbe95ddb5beLL, 0xbe467d4220a1cc9eLL, 0x5b4a4fd2f87ae1beLL, 0x345758b4e011047eLL, 0xdd58aea88f0f5148LL, 0x0c93bef8c6f515dbLL, 0x0686f0db53c51c04LL, 0xe315b0241edabb27LL, 0x5f83322e8e609516LL, 0x3b877ff62bd73aa0LL, 0x88beef6893258436LL, 0xdeb20e2dfccfecc5LL, 0xb5e1534e1dc36c87LL, 0x74e149330947db96LL, 0x6b32991d7bb55851LL, 0xbe3d9ed838a1e4f1LL, 0x84d2a8f76d417cb0LL, 0xf2c5e2cc73319f27LL, 0xbaa3001db7016b36LL, 0x43ff9fe3b8290749LL, 0x0c460dab58214fb0LL, 0xa7fe302c86ef1f0dLL, 0xe888cb0415dd02deLL, 0x364f20379f9b47f8LL, 0xc5c8e55ad13e4a7aLL, 0xdce7cfcd73a0dbe7LL, 0x51e3a00816117f63LL, 0x07fc0097d69755f0LL, 0x18e89bdb2110cbaaLL, 0x843d7edb454dbe8cLL, 0xf88c08652d037577LL, 0x6f5c3c247fcd1cefLL, 0x325fe99552473f97LL, 0xe11cf6edb9eb0a64LL, 0x887345371c93f7c4LL, 0xf13c9d21a8622b12LL, 0xfd92380821603f9aLL, 0xe0459b855188d045LL, 0x3e95a6143224d140LL, 0xddb6d903bd410212LL, 0xaca1b687ad9fb79aLL, 0x9ee4a085394013d2LL, 0x5d35c9d4be0fd1b6LL, 0x79d4dbf9d396aaa1LL, 0xd5e2f69d09b36753LL, 0xa3116e3dfb3ed68bLL, 0xc460a3e382fd1922LL, 0xc54d8b62dfb8f1edLL, 0x8ee64b5972f0c348LL, 0xb55d0404688df26cLL, 0xab675690026aa3aaLL, 0xd3bdc641379bdb23LL, 0xc2fc56f9e08f6d14LL, 0x233a70967a674e42LL, 0x400b1743c1e4e283LL, 0x25f194e6d9ecbbe2LL, 0x6ff4bc0d24ae0fa4LL, 0x7ee2f4b068b2bf3dLL, 0xcb72e68021dcd919LL, 0x3f934ce403d89f48LL, 0xb5c6d1fc29bbe67bLL, 0x5019cb39451dc61eLL, 0x78f8f1eeedf9493fLL, 0x99c192529caa0de6LL, 0xc1aa30de701667a2LL, 0x18bfe80bb560451fLL, 0xea690edacd6bab2bLL, 0x13462d8ca73388c2LL},
{0xf5058f8ba12f2699LL, 0x0a3949e6a1833e0bLL, 0xfd4bdd6786c17ceeLL, 0xe9e0c6bf8930fbcbLL, 0xef393b6b4260c75cLL, 0x228a994edfadf0d1LL, 0x1a6ae616243dcb1fLL, 0x775719496f39aa5eLL, 0x8851a402ec5f1de6LL, 0xcd547c56124bd059LL, 0x6c8391b5e522cf9fLL, 0x95a138c463826bd0LL, 0xe92088c7635be419LL, 0x6d9dec93a7978a24LL, 0x847ce1f9a68832e5LL, 0x892ebb6ecbe44a5cLL, 0x31d06448519878dfLL, 0x24cfd2b097eac62cLL, 0x9e09bede71ced048LL, 0xfb8f783d08ea6f3dLL, 0xba687bba8be3cd51LL, 0x0866899d9652c183LL, 0xe53368dcbcf4f9e9LL, 0xdf2a13ebccf56c8aLL, 0x9809f0d21da2e574LL, 0x4e1808d1d9dc75faLL, 0x2ef92294fc489d9eLL, 0xfe271c1224b3f212LL, 0x4cc8b018367e99e4LL, 0xefedabb18aecbed6LL, 0xc4973fd06e3d1a10LL, 0xc3213c90ec0ce939LL, 0x2e5fc1a14674005dLL, 0x5c0589dddc363d97LL, 0xf4d25540ed584887LL, 0x68954848fecc5d18LL, 0x6f13d0e31103696bLL, 0xd39a5284b5c33239LL, 0x298351a9a25de48bLL, 0xdb0cb7280fef8231LL, 0xa6452b7745d99eb0LL, 0xfc73d493e9cfc0afLL, 0x3cccf21245231f77LL, 0x9424dca8b9d4e32eLL, 0xb8d550a79b355a7cLL, 0xcb65130dc127364aLL, 0xffff5c695a440295LL, 0xe97a6f9e9c5fffedLL, 0x636a354a379922e0LL, 0x8d5af9d523859032LL, 0xa6e3ec95e729261aLL, 0xdaac2d7b1b61d569LL, 0x5440365193f0164eLL, 0xc648cc2ec2ef33e7LL, 0x09a9a9a478325b63LL, 0x39de2797f5237231LL, 0xbc7d982e961e4da5LL, 0x406f5f56cce8d1c3LL, 0x4ae00c4741ff78d9LL, 0xadee0607a2338b2dLL, 0x4e8fb4da142c57f4LL, 0x64f1774b9e0c5b2aLL, 0xad554e108341c6d5LL, 0xc2c43eedd605ed59LL, 0xbf9eb3c1cb8595bcLL, 0xb7c370b5ae33d786LL, 0x5a0a95553c9bee44LL, 0x72dcd619e0cc200aLL, 0xf4c3d1b3aa10e618LL, 0x69476c20a28b8882LL, 0xffa58dded71714c6LL, 0x1c1fce7fc536ae0cLL, 0x9521d4d4245f13ffLL, 0x5c4dd77552259578LL, 0x6a306ab54d5e816fLL, 0xf4d7ee4c199bb2d4LL, 0x6d53e0cf159a5da8LL, 0xce71205a355916cdLL, 0x1a9a0626a035fb9dLL, 0x66b49b5082a97d65LL, 0x67b3d5902cc32dfaLL, 0x2c3b0cf6fcf989afLL, 0xc21a9d5730d89929LL, 0xfdde53690164a34eLL, 0x48ad9a7a90928361LL, 0x2513e52431d1b8faLL, 0x0407a7a2237b3916LL, 0x3d828026d2d3e328LL, 0xf362cd9e16e8270cLL, 0x3e17dec2e75fedadLL, 0xb6564872a8a6cf72LL, 0x3282a1f063a52f91LL, 0x24a83a6cc8f82d07LL, 0xbbda650eed781ccbLL, 0xb70a623fc3ab935fLL, 0xd7c15fd931f5de77LL, 0x8591fbe66b2c1c2aLL, 0x66816b94d0a99a7aLL, 0xe22c609206cd09d6LL, 0xe0d33ba4c00756dfLL, 0x9e3a38b1bee217eeLL, 0x4d9c56b2a1d77a0dLL, 0x07c541b918618e99LL, 0x33ecfb1e620bf413LL, 0x1867c22bbeacff8eLL, 0x20e331723ee6ec99LL, 0x183dd88b10969063LL, 0x02eaa179e4f80afcLL, 0x204058fbd5b28083LL, 0x604793a790e01553LL, 0x70eff3d912f4efd7LL, 0xff581b4f40ad77f2LL, 0x1cd493f12f80d3baLL, 0x16e4257180efbe40LL, 0x8fa8b03ac0d73f16LL, 0xe7102ed2360ec632LL, 0x44ccff7d1fd2784cLL, 0x90598927cd2afb76LL, 0x5a8bb9d5d8edc852LL, 0x730e5ba55af63336LL, 0xddc7cbd988dea3bdLL, 0x4fe0133a4161e13dLL, 0xc12422512500c887LL, 0x1db74666cc4f8cc0LL, 0x8dc386cd5baebc7fLL, 0xec59422ea9b5aa65LL, 0xa172b02d9da70b85LL, 0xca3ef74d0c7ca4e4LL, 0x8e3a52d351905958LL, 0xf2fb1d97812d2d10LL, 0xdb70c6e789ca809bLL, 0x8685bca7657f60efLL, 0xb2a2daeeabc63c81LL, 0xe0567b423ba1dd8bLL, 0x270ed05358ce1205LL, 0x61ea9cce12cc4917LL, 0x0a35b9db379fb571LL, 0x494a63fc85b9953aLL, 0xf4d547279fc8a9e5LL, 0x4d3b70ef9636f395LL, 0xfee512d38f89e7ceLL, 0xf0a1a9d65f1507b5LL, 0xb10f6b570ae99901LL, 0x7087264936126c97LL, 0x8f544bb676134293LL, 0x4ee14648503da781LL, 0x384049ce1e4c8e3dLL, 0xf338e11b7a3c32f4LL, 0xd8e7066eb9af4807LL, 0x2a74997917437d6aLL, 0xd6ab1c9a18ebb936LL, 0xaceedc60416515f8LL, 0xbb3f9ebbab0d6735LL, 0xf5be8bf047401e65LL, 0x4241ca5dcdf532c6LL, 0xf468f0e4f6c53701LL, 0xab4fa3fc2e5b2f37LL, 0xaf1db95ca0661697LL, 0x741a8658ef176c83LL, 0xa72e7a16137eb7a9LL, 0xf858361e8ba02c82LL, 0xa24dacfab6e5b6f6LL, 0x496f1e3ad7bd14d4LL, 0xd2b08f297e5b00abLL, 0xbef94d7346782d95LL, 0x712f523330576f66LL, 0x8bb1c689564d353cLL, 0xc87215b713059af3LL, 0x1dc9ae74453e2c39LL, 0xf2a208d6b8ea5970LL, 0xb30c3e928585505fLL, 0x1d3481fb2793ac51LL, 0x72b09604223d2520LL, 0x5e2d6850749e8082LL, 0x1b4a96f0add719e0LL, 0x0b4b2527733a6d16LL, 0xea322607c94f54caLL, 0x40660cbb6066181bLL, 0x1a4f75e93b70f0c5LL, 0xca1a47f1b236cb9fLL, 0x0da3bace2e3e96e5LL, 0xfd30029a25b600a3LL, 0x392ef165edb152c5LL, 0xf8454ad0f0250c16LL, 0x2c120a01ce6e5635LL, 0xc2163647788661f8LL, 0x9f74435088d26c6bLL, 0x5d414a5ca79ea187LL, 0x7a787391acc02757LL, 0x0d865554aedcf3e4LL, 0x598f27f05a561a0cLL, 0x888117505c3481eaLL, 0x855472bd43a7eb1bLL, 0x1b5e6eafe4d9319cLL, 0x7ba6dcc71952c758LL, 0xc409de0e72c1029eLL, 0xecddc38fe4bd9fa7LL, 0xf0fb3dea0e963a3aLL, 0xc74f56910e787eb0LL, 0x90990e5bc3373ca5LL, 0x0c5925d4837153a2LL, 0xe18b75fca5a03ab9LL, 0x57ed017f14efdfcfLL, 0x1f09cf860efb6562LL, 0xe3734bebd2721f49LL, 0xcd540b0ad76b6470LL, 0x52bf75758aa43077LL, 0xeaf57b4de7aec8f5LL, 0xfaf1f16fc0595840LL, 0xa1827d3281774f09LL, 0x0999808380012791LL, 0x0c700c2701b44eebLL, 0x8a0bf5239eed75c4LL, 0xaeba7d070739f5cdLL, 0x9627c35e41dc57deLL, 0x1249e0cfd2939680LL, 0x25208a3a026a6c98LL, 0xbc38c140f4b56f6aLL, 0x6b8f3169f6f7e307LL, 0x9c5965a47cab52baLL, 0x4027671d00ca1f99LL, 0x18e33a1e4ff30654LL, 0x02a3d4a87b3df91eLL, 0x131b43e970f44851LL, 0xafabd6cf773fc726LL, 0x1e00a4b9e25488f6LL, 0xda0b8e9b7337a7acLL, 0x23aae6eda8213ea5LL, 0xfd35f478f99b5b90LL, 0xa8490abb630820fcLL, 0x57dcf553bef4b6ceLL, 0x1ab7730df0febe5fLL, 0x25bc9aff736b80a8LL, 0x96136407b491b9fcLL, 0xdf942caaa74a1087LL, 0x9f6aa2d664891149LL, 0x903c49b977638cc2LL, 0xde981ab87e610f64LL, 0xd663ab542cf7e8ccLL, 0x3e320ddcefa295bdLL, 0x1009304267449d36LL, 0x454bf8714c0c92b0LL, 0x52f76cd402888d6aLL, 0x223e81b011e135dfLL, 0x296579134b854492LL, 0x028a1f17c7bd8eb4LL, 0x1dc1efc1b05f3cf3LL, 0x9bf0973d8c1ab8a3LL, 0x1bc972ca705323ddLL, 0x983eccc42bfc5cfeLL, 0x51ac0f2d6d2d92bdLL, 0x844480ed482f2d88LL, 0x3213c250d95e2415LL, 0x2e5e3198a6b4c017LL, 0x0615548ece7312fbLL, 0xea011e5d1e1378d0LL},
{0x0bdfd3c510d59257LL, 0xf5af20d4aa5290e6LL, 0x921907b86c8dcb27LL, 0xa05847e0ff2f66dcLL, 0xd90613ad64b0b907LL, 0x0f1a1b581f018a53LL, 0xb47cf4dda407db34LL, 0x8707cda12ef7ad1aLL, 0xb3c2e6c8ee2dff6aLL, 0x560177c335b90aa7LL, 0xd466044b86919c00LL, 0x94d6d21a1a9b5360LL, 0xb83cb7ef149a99dbLL, 0xc3dd714e8a42ac41LL, 0x1226dcfd37d1666fLL, 0x70a83b2e156759b0LL, 0x8365b37b7e6354e8LL, 0xf1fa3503af110c2bLL, 0x1154693004216e37LL, 0x1c548ebcc331e718LL, 0x5d6c360e8788d133LL, 0x7e6de39d7e3a2110LL, 0x71ef83f7f6926f13LL, 0x8fa226bd22c35b62LL, 0x576e115bf560b4afLL, 0x98a16d274bb044d2LL, 0x41ec9f7fd62fecdcLL, 0x7b698aac1250e362LL, 0xdf11039fd9be85a1LL, 0x43f3316d8edf775dLL, 0x3cb320009e79d8c6LL, 0x7bf8285d8eb89465LL, 0xb955e75035e7fcfcLL, 0x4d3abe3aa16215baLL, 0xf04a3a5a5d719fdaLL, 0xd725b8a042d2b5d1LL, 0x0ebec6a59ca2989fLL, 0x8eb6a02c0587e87dLL, 0xc06f950e913ead4dLL, 0xe5b13994a6b82a41LL, 0xa544eb82529ba4a8LL, 0xd07b3a6674b96867LL, 0xb7ab8dc5da20e2afLL, 0x6159552a9eca68c9LL, 0xd16ea7b3deb06e32LL, 0x3f282ac397f2f34aLL, 0x0172dc4297080c98LL, 0x21b602dfc333189fLL, 0x39ad826343c780deLL, 0x2728a3a54aa9efffLL, 0x82649f8b543a87bdLL, 0xf907e529a236960fLL, 0x69b4864b32b726b5LL, 0xfb475f5567485469LL, 0xbafec212b292a9bdLL, 0x96921ebe46d4dd33LL, 0x5bcb3425d150cfa7LL, 0xa209e47b000ad3fbLL, 0x019ced7170499e94LL, 0xe435bc7fab9f16e7LL, 0x1098f0ddd90a87dfLL, 0xdf13872fe069c162LL, 0xa974c09df16cd92fLL, 0xe3dd32dd4d187e50LL, 0xa0d4f3dc6d5f31a5LL, 0x5d035206f5d1347dLL, 0x5ecb516880284193LL, 0xbd90c1414a73e1fcLL, 0x5c774f7aa890fe22LL, 0x7e7d7b1d216ca887LL, 0x12be1f03b49ae75bLL, 0xddabda16a8fb8daaLL, 0x1507366a5310e7f1LL, 0x70ffd90fe649e7a1LL, 0x4a152261464f2386LL, 0xcb2786735423c8adLL, 0x5ec58bb018ab88d9LL, 0x7b53015f7cc5494cLL, 0xac1952a1b1675a17LL, 0x26ab44efb54d1686LL, 0x5839f9a01215291aLL, 0x8e0745b13c373315LL, 0xecdb8197ab877cdaLL, 0xcf1844ded0fc1107LL, 0x6f06879877e05eddLL, 0x77a617cae5a2a0cfLL, 0xa9d33f813b354428LL, 0x294770316e546926LL, 0x1cf33d08a47df497LL, 0xae070dbadef65c04LL, 0xa49d37b24e47f922LL, 0xb1a417f689f31ff5LL, 0x35878c4649122316LL, 0xff1ce3ba9b7ea6ecLL, 0x62cdf75610201e68LL, 0xad61e0388a97905eLL, 0xbc419022580a828fLL, 0xf67eb026df6fbba4LL, 0x3fca2b1d0303d91bLL, 0x83d472ee97d9a017LL, 0xbbf5b0447bcecf93LL, 0x241e5b3df37cf896LL, 0xfcd0b25f9f0810aeLL, 0xf192b9930e61aa2bLL, 0xac58e4ec2ff65d5aLL, 0x8f8a24cebeeb31f1LL, 0xabaff16af62d7736LL, 0xdabdcf858a4a856eLL, 0xaa72ffbb9ed20b93LL, 0x644e81d6a8309dc6LL, 0xb42f7bf190d05835LL, 0xc214800eac48589cLL, 0x4e6b65947b2ffd40LL, 0x1f52517fd3eccd23LL, 0x16e3e0249244a1caLL, 0x11fed6d19d9b8f0dLL, 0xb764ca193353896bLL, 0x5586199f4ee374b0LL, 0x541c7af9753fe1feLL, 0xfe2696d60f5a2c91LL, 0x18370d70a5a97423LL, 0xdb311790dd551dcfLL, 0x235e11f95345ca4dLL, 0xa2824a65af07616dLL, 0xe9588b54751530e8LL, 0x3a79ae5fcdec455eLL, 0x378fb2f08d8cad6dLL, 0x8ab1c45a84e890bcLL, 0x18111061d555a058LL, 0x991fcbbdd85c02aeLL, 0x3769cbac68c764efLL, 0x162d9f456eab2237LL, 0xd9286b0fdb9149d2LL, 0xb56410e1416ef97bLL, 0x83ef7afc9d7d0c78LL, 0x79ce50017f66a69eLL, 0xa4e2c82f4e655a67LL, 0xb4b91895ca6aa96aLL, 0x2deab196a0bbb465LL, 0xa4c75f361c647328LL, 0xd13f307df1b7bda4LL, 0xbb37f24dffb27ec6LL, 0x2c27049c2e924c5eLL, 0x83ef6fc03ca691afLL, 0x12ffa86cebaab300LL, 0xf15026a592a90f73LL, 0x4d9eb1ef2934f2feLL, 0x69aa132e2a49b299LL, 0x99bffd8837f06f11LL, 0xb1896ea7409a8aa8LL, 0x83a466fdb65baeb6LL, 0x82a736a82a39de6eLL, 0xfa483af9034ef6c9LL, 0x20ab964335d27ffcLL, 0x98f76e4591869c25LL, 0x2b060ba26df804baLL, 0x2b3d9291d1c65ac3LL, 0x5769fc550f452ac1LL, 0xcd5fb5b0185e7b43LL, 0x352d121ede07fff2LL, 0x8a0ef9d8a7975d16LL, 0x6d453c06f1b56a9aLL, 0x34b8c1e3c03cc5e4LL, 0x8474335f96fef440LL, 0xb708f3ceb05f1e0cLL, 0x7603b0fc59aa2ed7LL, 0x189e421cf030024bLL, 0x257e01bd066ae050LL, 0xa29a61d3e06a6e05LL, 0xcc1d43d26250ce44LL, 0x4b0ab6ebc18c0fe0LL, 0x2cd0abded3c57f12LL, 0x3a9353a83b55a1afLL, 0x6caaaa181fad098bLL, 0x8b9fc9b1c4bc42f9LL, 0xea1d0b3d89d1ba1bLL, 0xd997c347bf062678LL, 0x5055cd9ab368f7e7LL, 0x2e1010f8f95e72ccLL, 0xea278945ac94db0fLL, 0x244af15ded1308a6LL, 0xa3325008beb11ac2LL, 0xea50e69878bcb62eLL, 0xe7c88d9262b0f6fbLL, 0xa21c101e34899375LL, 0xf3bed7219d80466eLL, 0x2335330e1234b102LL, 0x1ef14a9a09e4ef97LL, 0x35bb46ae64db9679LL, 0xe4dd0aa349d5a2ecLL, 0xf78fccf966dd588bLL, 0xc0f440df32757c23LL, 0xe7cdfc8ac4f8da63LL, 0xb935c35b8cb17d9aLL, 0x2695595470f9a33bLL, 0xd19362cbed2fd7a4LL, 0x7e3307c3a85f1abcLL, 0x4f9a98558b0e99d1LL, 0x1b6fc0e475115b08LL, 0xcf9bdf01f2f43e6dLL, 0xc2ec0c71ed70cdfaLL, 0x63da0f80ec6791fdLL, 0x8b618bd9108d7344LL, 0x5defd5ae717f9b51LL, 0x3297427a279aef6cLL, 0x71f3d9066a60b28eLL, 0x0bb70771108a9d06LL, 0x20005c7c7653c9edLL, 0x2461b4a0bcb4cc03LL, 0x395fc6d34d7f0fd4LL, 0x46255aefbb97ff1eLL, 0x088a99a8cc53b4a9LL, 0x51620421beef2350LL, 0x6597f5c0db930c97LL, 0x49de5ea853259719LL, 0xd6598b8f6d3a4beaLL, 0x21164ea628dca821LL, 0x58b5442158daa9a4LL, 0x7a8afd852673dae3LL, 0x155debf84c17fde6LL, 0x1dbe6fa406de0791LL, 0xb42ed447d865e680LL, 0xc4b89d77e9b5a4ddLL, 0x5f1a50cd1f31d039LL, 0xe6807497dcd9eddeLL, 0x400e3aa8d2b1b8a9LL, 0x701a159711df3055LL, 0xd25ea25b8c354317LL, 0xf68ac19f01408e08LL, 0xcc7333ea029cfb20LL, 0xe87a614c25d3298cLL, 0xf7c609b078499a6cLL, 0xed1eb0ab64976ef0LL, 0xf555c97ca8c32a4cLL, 0x735f95d564bec6daLL, 0x2c265ec10962d680LL, 0x44651f571c759875LL, 0xf1ed9c52c7111b1dLL, 0x87955bd9f573cf88LL, 0xacda1a35857c82f0LL, 0x7c38564aa062d6e5LL, 0x1b3b4dad09afb918LL, 0xeca937c66bc32599LL, 0x0d2e1ee0f6e7a2daLL, 0x5b7fad4b796414e7LL, 0x2ea99bcf9b9830edLL, 0xb02b7fa90b1426c7LL, 0xe1cd443cb66563ecLL, 0x75022601470863fbLL, 0x105a09103198be24LL, 0x9db1705965b4bc14LL, 0x6cfe872de5a36651LL, 0x2816e06b206fb845LL, 0x04cd4d1a8d50f2ebLL, 0xdeb71787bf7c0e42LL, 0xac7bb0da39f9a8c0LL},
{0xb289dec7c67211d1LL, 0x8973264bb4e2fc0fLL, 0x2ce303548e21ca91LL, 0xe4c149b85e815c7dLL, 0xa5bf00840b8e66ebLL, 0xee083ac221ce8d37LL, 0x267f39ee764b011cLL, 0xdc72dff9cf521ce0LL, 0x29958bffb363beebLL, 0xfb723910db1ba100LL, 0xbf565befb88debc2LL, 0xca6de109d088ecfcLL, 0x5984c1b54a3cc65cLL, 0x6f73499f91433434LL, 0xcc7cd48dda9472daLL, 0xda7c85a37be19f04LL, 0x201e30b6be1b6d4cLL, 0x2f00ced614700c1dLL, 0x7afc6400684a1d73LL, 0xf5a32d25dd679e92LL, 0x4b0365c3c7c7e67eLL, 0xebddb82c0528562dLL, 0x2a1d40bb44bab938LL, 0xbe83d373a40c9ddaLL, 0x0d6f9893afb6fbd2LL, 0x0f339a97fefff496LL, 0xef5156be92ca0c45LL, 0x88404f1e1907cdceLL, 0xc1ee09a27e61dd37LL, 0x614ea7c8290c2d1bLL, 0xa9d77303399706fcLL, 0x868f76161edad101LL, 0xaeff2231ac200f6dLL, 0x46bc7a54793f9eeaLL, 0x2f2bf82bd675bf4fLL, 0x2e681a97fa0a022dLL, 0x80ca111cd957e421LL, 0x197f6f28841c29a7LL, 0x64a6c8e42a620290LL, 0xbb6f08032a81a871LL, 0xf35e6503c7793586LL, 0xb6f3973607e4dd19LL, 0x060c99dcb5ba30eeLL, 0xd6bd5b3ab8692afcLL, 0x7a7f32d1c772a919LL, 0xbe1daee0f5d7ecb6LL, 0xf7024d8db0724639LL, 0x1eb4933aa3c1b97eLL, 0xb8391138dc053708LL, 0x383ad3c901ac7366LL, 0xf44ff4f544009fa7LL, 0x5786110d6009fdffLL, 0x81f993d3ee0cc6fcLL, 0x2a81c39a7a7167ecLL, 0xa4b2722fc5b7e663LL, 0x3e106ef9fa8dfdbeLL, 0xf02bdbdbf868dc2fLL, 0xa15a4ed6e472c4b9LL, 0x578e6994a320382dLL, 0x240b6ae7f3a0f143LL, 0x8858c7e65e0d33bbLL, 0x48ec589363b0ab86LL, 0xb4c227e2319199a7LL, 0x1143b94ed93bb9b0LL, 0x98ebabbe5b57415cLL, 0x4623e8a90123aba0LL, 0xc5925fe13f44a8caLL, 0x80f85b81f150c4a5LL, 0x5257efe07cf36239LL, 0x7a796e0c6630092fLL, 0xc5b2fc8052a4e56cLL, 0xfd717d77915b0e67LL, 0x3720f7475dd22a86LL, 0x9ddc4f2c48f9010aLL, 0x41bbf7fe55611187LL, 0xce787bf65aa70a5eLL, 0x61ef28358e606d4bLL, 0x0c4c63bbd2418249LL, 0xba9548b88cd5f401LL, 0x75847d5f226da9a0LL, 0x9568335a673a2c54LL, 0x8810c41a60de1664LL, 0x073747596aacc32bLL, 0x1e65a9a9d1cf923aLL, 0xe1a63ef73f0ae133LL, 0x5d0fdf859bdb4a9eLL, 0x891456db52f67481LL, 0xfb7d31da7fc68595LL, 0xebf10ae5fb5bcbc6LL, 0xe1b579e66d370beaLL, 0xa7ffe9673d6313c6LL, 0xc7ac788725808efbLL, 0xa72330eaf8838691LL, 0xcaff131055720f18LL, 0xec5b3fa7ca7ee767LL, 0x29fadc6690ed3bbeLL, 0x393871b366a5c883LL, 0xa3e00d9d75278e2eLL, 0xcb70a05fd3a5551eLL, 0x7d71e626c4742a37LL, 0x9787211f7582a812LL, 0xbce686f53dc831bfLL, 0x6b7989a96c774433LL, 0x796261baf2b9a58bLL, 0x2ae598b7024cbd9eLL, 0x2a1cccbedb30a20dLL, 0x7c132411b7ccf5a3LL, 0x4cfe0e8cef307947LL, 0x8a1bd2438e77979aLL, 0x822ffd1278403590LL, 0x2b7bf3c02152a311LL, 0x851725ad4c8f3386LL, 0xb9c2da6fee6e0135LL, 0x7a4acf8ec0724c29LL, 0x21bc86a875ee10e1LL, 0x3b9e0ecba4bbdf7cLL, 0x7097945f6db1b2aeLL, 0xc7afc89ae663ed1bLL, 0x0a36e7a027143e14LL, 0x024cd76129e8f848LL, 0xd72acd102b31075bLL, 0x902674b3d23de8d8LL, 0xbd595915259343b2LL, 0x2d7bd8cef8c12615LL, 0x04915788814420d6LL, 0x7e17983f59332a90LL, 0xfd78a55114600229LL, 0x82adb2ea6a66a84eLL, 0x0d13703b928bfa98LL, 0xacfa7a110214c5aaLL, 0xf66915712bae1d6fLL, 0x49d6d2da3808362fLL, 0x1d47984cc40469caLL, 0x5a716e01ba3e546eLL, 0x4276cd33c7b078d5LL, 0x4336ceeced824f79LL, 0xe7877d4731f90737LL, 0x6e7a37e8e93882c4LL, 0xacd0350a7148e39cLL, 0x2c5ecc6285287019LL, 0xb06e845a9c112685LL, 0xe1909082d8eabdd8LL, 0x3f641546e8bbb5cbLL, 0x088ecc151eb67677LL, 0xa538fa42a8a5f50dLL, 0x97dc8d33aa00132dLL, 0xf68773680ad3010eLL, 0xd695a0b76d526099LL, 0xc351a2a099cfe08eLL, 0xefd66119b5d757d8LL, 0x4d088c1f65fdd4daLL, 0x710515525ce9602cLL, 0x7f8a89c107b06181LL, 0xb327a1ee82c502abLL, 0x76f79771ede800ecLL, 0xc751e2b4c371b5c2LL, 0x66bfec8de907146cLL, 0x56297db5fd5dd727LL, 0x751f67bcae322fe4LL, 0x56b9c72a2f06b4b6LL, 0xf7b851ddb2b497f7LL, 0x3a9ca955c820ca5bLL, 0xb0770b0ca784e241LL, 0xeb1377831ac3002cLL, 0x5e4b09e018a2380fLL, 0xe3bceed54005d667LL, 0x25fc8fa23bdf646cLL, 0x572708614f42afceLL, 0xe53d48a636f0c119LL, 0x5defc8242fc7e5b3LL, 0xa2766e5453d031a4LL, 0xf314097bf7b8ffc2LL, 0x38794e2c7ab44bc8LL, 0xd6cea8346373fbdcLL, 0x2d476673d81442eeLL, 0x4d4665e081bb56c1LL, 0x5847c62f24196516LL, 0x2d59d2a0cd9f68c5LL, 0x2c2af3098ca4f11eLL, 0xf2d8d5128f4e9e6fLL, 0x4db8e501222a043dLL, 0x29f4b1052bbd24d7LL, 0x443e4a48d0c6859eLL, 0xeab955a85bce0023LL, 0xf46138efb30d6e59LL, 0x3c9066668c347316LL, 0x8a0a762c1fe8db23LL, 0x220dfdb10006af7eLL, 0x9d6bb82c4f4283efLL, 0xd6f32bb302525f4dLL, 0xb5e92c6ba98841b0LL, 0x4832a1d58fd6eab9LL, 0x63fc7becebd00620LL, 0xf71b6efa0cd349fcLL, 0x27932ef532755cd2LL, 0x97e204e3ad08e82fLL, 0xb00165229f9754b8LL, 0x999a5d86fc08a770LL, 0x9091ed175a588d78LL, 0x30e112ee7117f8acLL, 0x23c711f7e1e5c27eLL, 0x630396b6aa58c8b1LL, 0xd8599db20e0df5a5LL, 0xa08d8f3d6d0a447aLL, 0x2af44688b28b3f60LL, 0x07723a709bdfd1a7LL, 0x72e4068899bc55d3LL, 0xbf8c55bf1eed0e60LL, 0x6d7c57be9e7ce73cLL, 0x085666de45f74593LL, 0x2569450763498af4LL, 0x915067c0aecae206LL, 0x7bb491df3248309bLL, 0xa55badcc79e039e0LL, 0x5df63adca0f451aeLL, 0xd4e83d760e0a98ffLL, 0x2110db192ed51772LL, 0x4fea258c876698a0LL, 0x97f3fa351850dff9LL, 0xb78863063e8988b5LL, 0x1388e7ab58145fc1LL, 0x4b5c34f3c6b0099cLL, 0xba2f3283d754485bLL, 0x0d9670e9659e4434LL, 0x0e4e2e3cc4b6e134LL, 0x199a058eca7d0b63LL, 0xa648782e29a808f5LL, 0xe537863c1f247f9dLL, 0xf20b43f8a9017916LL, 0x7cb38fc2fcfb47b9LL, 0xb9720ebde8a5d3a7LL, 0x032a49a93f736987LL, 0x639372a20c6515c0LL, 0xc2f169d13944b39eLL, 0x72de808b5c97e4abLL, 0x311caa28169c9bb8LL, 0x3ad1f1217d8dec66LL, 0x29d0dcb741bd1256LL, 0xf897997d40c09cc7LL, 0x1af2fc7e78b4bdd1LL, 0xe1baf3c816672f9fLL, 0xc1f9a68e4a6b4ecdLL, 0xb84a5dc3668d8572LL, 0xdef7bfaa198a3587LL, 0x04056455551e9b5cLL, 0x31900e5bbd5cf332LL, 0x598f822c9577529fLL, 0x03e60ccc50315ef9LL, 0xc683e863900f3308LL, 0xaf414114abfb66b3LL, 0xb663ab5dd93e17b6LL, 0x30864838a5ed4aa1LL, 0xb84f722237786928LL, 0xdf3621e039f16669LL, 0xbbd2a42495394733LL, 0x6b836652699f9878LL},
{0x569bc711ffb79e9eLL, 0xaf4a8d26492be221LL, 0xc0d023d8f671041eLL, 0xda319f011f2b0896LL, 0x2d9739a532f6d062LL, 0xfcead7b26ae8cae2LL, 0x2cab296df60e7114LL, 0xa2ce7a9968e1aba8LL, 0x94346e5db4d88d67LL, 0xd57a3d2bb8947a30LL, 0x71a5c2c186e78145LL, 0xd2ef0ac17d8ce061LL, 0x82cb777c443c8c81LL, 0x3b064208b9186a62LL, 0xa6dbc4233a9c45f8LL, 0x0681453108535adbLL, 0x07a838ac57d8103dLL, 0x03c8a3993e7c45a7LL, 0x8e7347594593fddbLL, 0xd3e5ea64ee000decLL, 0xab18a9dbf6c8b7f6LL, 0x01a4e43618f32203LL, 0x76a67ce0ce9d4677LL, 0xfaeb822c307820e4LL, 0x13a1860f7bac4f8fLL, 0x45626c2fe17525ceLL, 0x392f2bce314bcdd8LL, 0x7a6879a45ba13c5aLL, 0x38b2f8c39a0f509dLL, 0x93211e61097c875dLL, 0xbc6f2c6cf78b25aaLL, 0x1435f45339bbbf9cLL, 0xd5cab07e5e5c7986LL, 0x9c30e309e483e87dLL, 0x6033b4226e1590feLL, 0xe78348a4c0d82523LL, 0xe9dc0872abae1f8cLL, 0x79af7c281de11067LL, 0xa265e819a0a2eebaLL, 0x2041050a133974a4LL, 0x9d079bc370b4ff0fLL, 0xa6c01dcdfcc36028LL, 0x5239b96dc1e26c96LL, 0x94a6ee034fa4b7c8LL, 0x2ea15370f12d5bc2LL, 0xa1339bebeb06b436LL, 0x7b316646e2bbfd88LL, 0xb78d679dc3c45746LL, 0xd2a5e96cc48ad103LL, 0x720830c8178b0265LL, 0x7f894dada9477db0LL, 0x43f2db6005b5e413LL, 0xc26e4cb40cc5c717LL, 0x93595393f5f708ceLL, 0xc509726ac665ed55LL, 0xe28e924f98759618LL, 0x8a7bf0a34ee11da5LL, 0xbdba37d2cf5150cdLL, 0x4606d93b1d5e792dLL, 0x03f12ef6eb28e0a5LL, 0x657a4d002aaf6474LL, 0xa27100143e809068LL, 0x22ea86ebb262af66LL, 0x1bfa3206406f9db2LL, 0x6a2e10f657f8c989LL, 0x105b779d9d378947LL, 0x22377c20b5cb77dfLL, 0x91caa9678844b830LL, 0x8a91ea5f13991ddaLL, 0x62f64062ea52d29aLL, 0xce43ef428dafd1d9LL, 0x657425ceff6e3817LL, 0x169e3bb4a1ce5ee0LL, 0x9dffc29c008ae7fbLL, 0x624587cde869e7e3LL, 0xba929fcf9f26d01fLL, 0x79d9bd2acb45855eLL, 0xc4722e1104c46a7cLL, 0xe38bda7d683b0956LL, 0x59d28727d521c3bcLL, 0xfa433948b95607f1LL, 0xb7794e1c1305ddcfLL, 0x2012ada0bc0f2dbeLL, 0xb11b9bb5aa9338f4LL, 0x5710df106e6eea09LL, 0x8aff33f282ca7be0LL, 0x34118964b86ea62fLL, 0xea6dc4c66ea67cfaLL, 0xf9156b64be42f536LL, 0xa8af849bc84a687bLL, 0xdbacb200dae8ed88LL, 0xa12e011b53fc6782LL, 0x179d830cb591bfc6LL, 0x540c908cc7949182LL, 0x1894633f3ad346c3LL, 0x3f8d97286d7a76ccLL, 0x4d8cfe72db5ddf8aLL, 0x701a01e7f84f6afbLL, 0x6fdbef12f40a9cd0LL, 0x61cfbc01631bedfdLL, 0xf90e1e3c51425612LL, 0x5fc114e33e01634cLL, 0x50b4877e99b94c13LL, 0xf9920d4d0bced5d0LL, 0x04fecf3d5e0b9baaLL, 0x59b76ec19a76ffe5LL, 0xd9c316d1b2650803LL, 0x3f5b41e1e47a4d3aLL, 0x4ac202cc63c46212LL, 0x2fb41bf326716546LL, 0x79037ff433ce3a56LL, 0x01f8eae3905ec5b8LL, 0x28e4f68b82ea1bfbLL, 0xb530fda3bdd00876LL, 0x2a8e81ba4230a933LL, 0x027ec8a25aefd8ffLL, 0x7b6c125c5e90571eLL, 0xbf2f694284b54a4cLL, 0xbc72c44a2d37b9f5LL, 0xdc617fcb07124f45LL, 0x3741e258f0f259b3LL, 0x4a9ac41c7cc490c0LL, 0xfdf6efff33e69566LL, 0x6ddaeddf7800eb6dLL, 0x2074cb9c6115d50eLL, 0x2b3c4d0dc42b29dfLL, 0x4a120798a369a893LL, 0xe437d86beb834ce9LL, 0x3a3d63e9dfd7932eLL, 0x59836fc76dd0917dLL, 0x8702704f008f3c35LL, 0xa48a670b8bc7b08bLL, 0x89c844cea438741eLL, 0xfe28d82a9394ee25LL, 0xc06ff73116036b90LL, 0xf65222b70506915cLL, 0x81b2012c365624c5LL, 0x3fd73792287960d3LL, 0xddec5556e1ae9657LL, 0xbd0e4600da49d374LL, 0xef138630d01db912LL, 0x7c134005d9c10d93LL, 0x44c7e2defc8c9576LL, 0x146bf6e9ddae1d14LL, 0xc8e110865e7bc3eaLL, 0x48ac5dcdb8756690LL, 0xecd3285717a8686aLL, 0xeed05e8610b487baLL, 0xe5bdf00c49a11bfaLL, 0x988b4cf711a91036LL, 0xcf3ba62a30ceafccLL, 0x11e97bbfa012bcefLL, 0xa2f85a5409cfb966LL, 0x24349d1ef439e5ceLL, 0x6ece692f4acdd752LL, 0x07231cb6c5c99af8LL, 0xaf2afe7f2db3637cLL, 0x2329f3c4b7a86301LL, 0xad08f0e50ad319d1LL, 0x97ff4a649879cfb0LL, 0x23d96951158e67f4LL, 0xee38444ccb4b3784LL, 0x6529a6f2fefd12cbLL, 0xe38cd4d21982a761LL, 0x36411f97cb99cbcbLL, 0xac29e1f2bff431dcLL, 0xf68711d3aba4a975LL, 0x02b1abe5a430549eLL, 0xc2b409343057402dLL, 0xc2b715613f463eabLL, 0x818c11d800b20d56LL, 0xe714b274ea553d24LL, 0xfe95b143802286abLL, 0x59cc71773452b152LL, 0xc0c1c20fb16ae7b6LL, 0x7307632c9717e0faLL, 0x768c573526582e20LL, 0xc12efb048e2358ceLL, 0x7ce49e73a04b3046LL, 0xdc410af471774101LL, 0x66136c158cc59de4LL, 0x82b53d686dfad71eLL, 0x7e529b1ee08c22a0LL, 0x16e67b9686c76439LL, 0xf2b2d43e3672214cLL, 0x214043a604ecb92bLL, 0xd23f7df4ca82887aLL, 0x75ccf22e3bf0fa05LL, 0xaa82b5fd59ad2b87LL, 0x0058fdfb3c29ef7bLL, 0xb1c42e3bcd8eff50LL, 0x2d6946332642b11aLL, 0xdf202f6e454f1af9LL, 0x6109a6551bf02e82LL, 0x817b0593afb4ee63LL, 0xfeb6351f7febe673LL, 0xbecc08d33f44be5bLL, 0x6dd83205c6fc964bLL, 0x3b22257653a666e9LL, 0x94c171a4a3c9080dLL, 0x0413589db504846aLL, 0xa68b019e7560eef3LL, 0x3c03da692d227f7bLL, 0xcdf08f40dfae129cLL, 0x742548bd66122b14LL, 0x6d266b95c1eb66ffLL, 0x2cbfb2ee1ba03b0dLL, 0x1a8c3ace6d61b451LL, 0xf252c520c7ffffaaLL, 0x30e32b7949319a61LL, 0x9c1bfe3e7edc2141LL, 0x856bf71cbb890652LL, 0xbcfbbb3158708337LL, 0xc1997491831e99e8LL, 0x5ea496743e35d616LL, 0xab1c841314fe3778LL, 0x966b4e76365bf3ddLL, 0x9273b47bfe18d6e1LL, 0x883f3f4095fa0501LL, 0x6ca6cdab0ceea2c6LL, 0xa6aa023b195f9bcdLL, 0xf31c97207b341211LL, 0x40e118c8cc28b167LL, 0xa186b58fc8a84f28LL, 0xf3cdb08191a1b635LL, 0xc8ea5070f16d660aLL, 0x533d667d0662f949LL, 0xab386480a93353e0LL, 0x83f07fc7c0049adbLL, 0x226eda879bf1e406LL, 0x6cebea9d100eff5cLL, 0xd70109afecc6211fLL, 0xf03397621586f274LL, 0xe8be37d165fa8a2dLL, 0xed0ad063953c68b7LL, 0x5f115562669e235dLL, 0x10ead01c47abafe4LL, 0x6fb579c82ee313a2LL, 0xa4529cf00230cf58LL, 0x7f6b3e796954b6baLL, 0x0afabafce04c1f7bLL, 0xec2923b7a3a46b4eLL, 0x90820d750964a8f7LL, 0xe147df510c0a84eaLL, 0xbcb848fb8d6769e5LL, 0xb298faaad0b253cdLL, 0x51a2d1388d22ed1eLL, 0xf2dcc19081306915LL, 0x4bbd2bc99823cc12LL, 0x284d5584cb20ecb3LL, 0x8da539d495ebf566LL, 0x82a766a24751fb61LL, 0x393f5b1312d7293fLL, 0x0507ad9aea974f47LL, 0xb8c0f27740afb625LL, 0x4f7ce57ebbc6bd44LL},
{0x6b75fb88b99862c8LL, 0xb7b956921d20fea6LL, 0xf1135d83b4a63920LL, 0x3ef072f4b5707dfeLL, 0xf485d909d2f79451LL, 0x57d03c5e5a815236LL, 0x184cd033e05db21cLL, 0xbe34cdd501124a63LL, 0x9c1d932fddc43ee4LL, 0x115cc1e744c02b29LL, 0xf7b1f7852343caf0LL, 0xfd44a6d045d2e776LL, 0xbd145094d19bc51cLL, 0x4aa4aaef3f0281beLL, 0xaeae565200f81f97LL, 0x191f75f4e92b276dLL, 0x11ae19296779e101LL, 0x1eb6fb2d05207b5aLL, 0x7a58634a74e425c3LL, 0xa1ac53bc5e27a37fLL, 0x535856db62acea07LL, 0x22b5b5dd82775dd0LL, 0x45d1fc579b7dbfe4LL, 0xa54b4a5bc74f5e54LL, 0x565db5a45e759655LL, 0x9dcfbce92e622ac0LL, 0x4fe61e7a6ace198fLL, 0xe57a6c2abd113d9aLL, 0x9fb0301fe9ecf810LL, 0xa3f14350569fa54bLL, 0x2ac016ab0a593addLL, 0x26944545f3f89de1LL, 0x128a14b4ec844defLL, 0x4be92e27e40fdbc8LL, 0xf86b4821e8fbe8f7LL, 0x0dc329c82b50591fLL, 0xc98436fa651c0128LL, 0x08addeee67884393LL, 0x9d871b331d063079LL, 0x361b353a841fef30LL, 0xfdf2354db957669dLL, 0xe23ba4fae0754c48LL, 0x205c035312d7b683LL, 0xac8ffed9051a9cc0LL, 0x11295dde666bffcbLL, 0xd268b716c19bfaf9LL, 0x96c756aea28ae316LL, 0xc8b1f10f015d2a0dLL, 0x2211118f31da328aLL, 0x1a097ca4e1f0fd25LL, 0x4c705883365f12f7LL, 0x62aa9228b4d9b32aLL, 0xf0f3e5814fb36301LL, 0xeb8fd4de6e208b98LL, 0x30cc8063d9de5cceLL, 0x833c9d94ebc81b83LL, 0xad64a15695f38047LL, 0x6c7f4124ce0ed0c2LL, 0x64e1a7221754bc59LL, 0xc55a81458e315658LL, 0xde27cc338cf92e58LL, 0x735acb5384ce392dLL, 0xe6195d18cf8c4874LL, 0xd558366e6dbf4605LL, 0xa75b618151e132e7LL, 0xca88d95efa2ad13bLL, 0xf53c71f1a84abc8eLL, 0x5f15c6edc7b2e47dLL, 0xb9831b9ea47e75ceLL, 0xe783155817b0d420LL, 0x2742106e86ec16d3LL, 0x49e8f1809c6262e7LL, 0x7467550f242829e0LL, 0x79b8063a3160c23eLL, 0xaaa72850376bca92LL, 0x044837f6fc3dd58cLL, 0x71bff579ea293135LL, 0x975c1eb13e9436c1LL, 0x8932539e0716d61aLL, 0xbfa0103e01b61558LL, 0x48e9e7fd7862647eLL, 0x2f99e0927fadf85dLL, 0xb494fcfe817171edLL, 0xe9f7b90b6c0c4e29LL, 0x02cc70ad0a2f8b99LL, 0xed491c5d351c18f8LL, 0x686fdfaa840d009aLL, 0x56c60e005ec85b05LL, 0xc2c4f0d1a69ec6b2LL, 0xdb78f7a4db46a0b1LL, 0xe9701bcc400e16cbLL, 0x939f664f63d68a0aLL, 0xc5d039d169838863LL, 0xaee45bd87944d11eLL, 0x976d9cb4437b1c69LL, 0x2a35744d96691915LL, 0x121a0b9f2c81b5deLL, 0xada6b4122a04da3fLL, 0x25262837fca360abLL, 0xe15bdb8f1cd954edLL, 0x8bbd8f8948cb21f8LL, 0x694d3e5af6a5afadLL, 0x4ec6d6cda8de0cabLL, 0xff21113dd9daf0bbLL, 0x7ab7180a3e9c0e87LL, 0xe9d6a678fb2397bcLL, 0x6acdaa06123435d1LL, 0x1591edce20187032LL, 0x52ba3394881a1754LL, 0x054ed3bccf0b7e06LL, 0x432d207478391643LL, 0x855cd1d6f3a5a49dLL, 0x4274a8f9770187d3LL, 0x8a39f7977f80be5dLL, 0x3b895bf7218b218cLL, 0x29773dd3b823d808LL, 0xff914d219f6aa1deLL, 0x264d8e418fbc06d9LL, 0x4ae13c2afe2f0541LL, 0x50a5b0654285feb3LL, 0x9769855a2ff3f890LL, 0xa75cbf9e3a7d7b1aLL, 0xb2c17abc7a55e24aLL, 0xbf6341484106c036LL, 0x0505d65819d394fcLL, 0x128782ab878233ceLL, 0x712f99601dc3df46LL, 0xf9398f9db8dd85a4LL, 0xfc3f04ed1d038aebLL, 0xb16f663f47f16ad9LL, 0x2b5daf618c7a628fLL, 0x745dee4d962e0205LL, 0xc7fc7f1cc3668d22LL, 0x8191fee41ba2596eLL, 0x182b102690a2502cLL, 0xff98063e03fe5fc2LL, 0x83bccf203165f797LL, 0xd322d67ea4800de2LL, 0x411e5c5ffccf2732LL, 0x2ac5845c95dc2b77LL, 0x3587a99baa78abe2LL, 0x9446692412c3cb52LL, 0x8fe88c8285ea5baaLL, 0xcc2a6bf3af63ad95LL, 0x807125139ff0ac35LL, 0x2138c30da5d24d5fLL, 0x7ad281e0e8bb5f28LL, 0xa5c244ee669690a4LL, 0xa021d3b9ccdb8a66LL, 0x04860c2efc4c8097LL, 0x95226a83d0305868LL, 0x2546331b7bd3d542LL, 0x09b881490420f422LL, 0xc75be37367998ff6LL, 0xd9b3c681cf7e6086LL, 0xe6252487ec72b88eLL, 0x75067b2295f98de5LL, 0x30e65f57ca2aae6aLL, 0xbb27eb44a4871128LL, 0x7c182498ee3f2a81LL, 0x34668660f829132eLL, 0x16bfa80e2c4dc87bLL, 0x86035f0147107c0eLL, 0x415d2e61242228e4LL, 0x6fdf9777a91ab8eeLL, 0xe220051fa7de07bdLL, 0xab3f4d8971d1dbd9LL, 0xd6aca326a9e7bafaLL, 0xc829d631b71bcfd5LL, 0x2ae4a8b59db20da7LL, 0x95d2133d638aa951LL, 0x888cf099d65f4942LL, 0x9f6c738b8a4a39a4LL, 0x3f949cdaf75491a5LL, 0x196d9090a67f9054LL, 0x14bf71df54d81ea1LL, 0x0329d679667ad7a1LL, 0x106dca4a7539f8a1LL, 0x4b804ff34c5a936dLL, 0x068ae0465baa2f07LL, 0x106a46fbc10a96b3LL, 0xe05f4e5ee773964aLL, 0x11127cb104fd25d0LL, 0x9569a72a315fc76dLL, 0x14abb7ebba90fd11LL, 0x18acdc5ff48ff9beLL, 0xc865ad1ade9bab89LL, 0xc0b300d73d242515LL, 0xb32932d5c0ee9a1bLL, 0x910d2e59ab360c02LL, 0xef4d92e1124b207eLL, 0x902abfa851850716LL, 0xda58917ddcd78ab9LL, 0xcb8b6f934075d2a2LL, 0x9de9076ba5ec30e2LL, 0x378c850c8fa6b729LL, 0xd422b8a187162eb6LL, 0x152293f05608c0d8LL, 0x0a5dd3e2fb7264c7LL, 0x83f4d06b30a60f17LL, 0x3f826bd423d47c5dLL, 0xc951c85fb7aa9f99LL, 0xe628009e31e6b255LL, 0xb7697932ff1707f0LL, 0x0711d426477cbfc1LL, 0x9af949d1f2e5fba0LL, 0x126fdc8397856f41LL, 0x5ea8f4669d0bbb22LL, 0xb172b2949558cfcaLL, 0x2529a618b7d2561cLL, 0x443cc0ad9ffcee29LL, 0x1918b7b777c4b27cLL, 0xbfaec848a1061cadLL, 0xcf5615520534592fLL, 0x3ab5b3a10bd84fedLL, 0xe114b534d01edd32LL, 0xf890789bb010aa2bLL, 0x1bcb926294f66bf5LL, 0x3cc52bb2a8c8d9efLL, 0xf9dfadf7e4513e80LL, 0xddfb19b318f5c570LL, 0xf95b3f4ded88bb46LL, 0x8f48b9114d0e4c8aLL, 0xb15024afa570f709LL, 0xb7bc42aa86ec1ebaLL, 0x183655cb5e3405bbLL, 0x0cc5db80e40955e0LL, 0xadb2d8439174d3aeLL, 0x469a2ff8b33a5898LL, 0x428ce6dcf47e0066LL, 0x0e3ab3d067049b96LL, 0x870e12f2d3d4881cLL, 0xdc75360c5e797ad9LL, 0xf8e30bbc1df4c0aeLL, 0xc425f5c82dab36afLL, 0x072a27a21d50d77aLL, 0x7c37bfd09c9e03caLL, 0x14dcf6aaa8c36c4aLL, 0xec59338dbfc8e59fLL, 0xb0b609824435a2d4LL, 0xbd9af3781cda5b46LL, 0xb4e62c3f8f412e0fLL, 0x5cb14972e32576a8LL, 0x2efdad924f94f9c3LL, 0x9926639abae24461LL, 0x365646557656db35LL, 0x6cf50c58661faa37LL, 0x91fb45d85d9756b5LL, 0xefc728a3287158aaLL, 0xdf1631ba1c6ed34bLL, 0xa04fd8b4e3a89d14LL, 0xc5f52eebfbdc8e5eLL, 0x331fb7b795d882ffLL, 0x649c2ef7750d939dLL, 0x37de4eeda7e82d8eLL, 0x40a75fa5f87ea0b1LL},
};
template<int C, int N>
struct Board
{
char board[N*N];
int *buff;
int bp;
int score;
int subscore;
unsigned long long hash;
Board(){}
Board(vector<string> board_, int *buff_) : bp(0), score(0), subscore(0), buff(buff_)
{
for (int y=0; y<N; y++)
for (int x=0; x<N; x++)
board[y*N+x] = board_[y][x]-'0';
hash = 0LL;
for (int y=0; y<N; y++)
for (int x=0; x<N; x++)
hash ^= Hash[board[y*N+x]][y*N+x];
adjust();
}
void move(Move m)
{
const static int dir[] = {-N, 1, N, -1};
int p = m.pos;
int q = m.pos + dir[m.dir];
hash ^= Hash[board[p]][p];
hash ^= Hash[board[q]][q];
swap(board[p], board[q]);
hash ^= Hash[board[p]][p];
hash ^= Hash[board[q]][q];
adjust(min(p,q));
}
void adjust(int hint=-1)
{
hash ^= bp;
hash ^= (unsigned long long)score<<32;
if (hint>=0)
{
bool f = false;
for (int y=max(0,hint/N-1); y<min(N-1,hint/N+2) && !f; y++)
for (int x=max(0,hint%N-1); x<min(N-1,hint%N+2) && !f; x++)
if (board[y*N+x]==board[y*N+x+1] &&
board[y*N+x]==board[(y+1)*N+x] &&
board[y*N+x]==board[(y+1)*N+x+1])
{
hash ^= Hash[board[y*N+x]][y*N+x];
hash ^= Hash[board[y*N+x+1]][y*N+x+1];
hash ^= Hash[board[y*N+x+N]][y*N+x+N];
hash ^= Hash[board[y*N+x+N+1]][y*N+x+N+1];
board[y*N+x] = buff[bp++];
board[y*N+x+1] = buff[bp++];
board[(y+1)*N+x] = buff[bp++];
board[(y+1)*N+x+1] = buff[bp++];
f = true;
score++;
hash ^= Hash[board[y*N+x]][y*N+x];
hash ^= Hash[board[y*N+x+1]][y*N+x+1];
hash ^= Hash[board[y*N+x+N]][y*N+x+N];
hash ^= Hash[board[y*N+x+N+1]][y*N+x+N+1];
}
if (!f)
goto end;
}
while (true)
{
bool f = false;
for (int y=0; y<N-1 && !f; y++)
for (int x=0; x<N-1 && !f; x++)
if (board[y*N+x]==board[y*N+x+1] &&
board[y*N+x]==board[(y+1)*N+x] &&
board[y*N+x]==board[(y+1)*N+x+1])
{
hash ^= Hash[board[y*N+x]][y*N+x];
hash ^= Hash[board[y*N+x+1]][y*N+x+1];
hash ^= Hash[board[y*N+x+N]][y*N+x+N];
hash ^= Hash[board[y*N+x+N+1]][y*N+x+N+1];
board[y*N+x] = buff[bp++];
board[y*N+x+1] = buff[bp++];
board[(y+1)*N+x] = buff[bp++];
board[(y+1)*N+x+1] = buff[bp++];
f = true;
score++;
hash ^= Hash[board[y*N+x]][y*N+x];
hash ^= Hash[board[y*N+x+1]][y*N+x+1];
hash ^= Hash[board[y*N+x+N]][y*N+x+N];
hash ^= Hash[board[y*N+x+N+1]][y*N+x+N+1];
}
if (!f)
goto end;
}
end:;
hash ^= bp;
hash ^= (unsigned long long)score<<32;
}
};
template<int C, int N>
struct Node
{
Node(){}
Board<C,N> board;
int prev;
Move move;
int score;
bool operator<(const Node<C,N> &n) const {return score>n.score;}
};
template<int C, int N>
vector<int> solve(vector<string> board, int startSeed)
{
srand(137);
const int BL = 100000;
int buff[BL];
buff[0] = startSeed;
for (int i=1; i<BL; i++)
buff[i] = int(buff[i-1]*48271LL%2147483647);
for (int i=0; i<BL; i++)
buff[i] %= C;
vector<Move> move1;
vector<vector<Move> > move2;
for (int y=0; y<N; y++)
for (int x=0; x<N-1; x++)
{
move1.push_back(Move(y*N+x, 1));
vector<Move> m2;
if (0<x)
m2.push_back(Move(y*N+x-1, 1));
if (x<N-2)
m2.push_back(Move(y*N+x+1, 1));
if (0<y)
m2.push_back(Move(y*N+x-N, 2)),
m2.push_back(Move(y*N+x-N+1, 2));
if (y<N-1)
m2.push_back(Move(y*N+x, 2)),
m2.push_back(Move(y*N+x+1, 2));
move2.push_back(m2);
}
for (int y=0; y<N-1; y++)
for (int x=0; x<N; x++)
{
move1.push_back(Move(y*N+x, 2));
vector<Move> m2;
if (0<y)
m2.push_back(Move(y*N+x-N, 2));
if (y<N-2)
m2.push_back(Move(y*N+x+N, 2));
if (0<x)
m2.push_back(Move(y*N+x-1, 1)),
m2.push_back(Move(y*N+x-1+N, 1));
if (x<N-1)
m2.push_back(Move(y*N+x, 1)),
m2.push_back(Move(y*N+N+x, 1));
move2.push_back(m2);
}
Board<C,N> B(board, buff);
//const int BW = 512/N/N;
const int BW = 900/N/N;
vector<vector<Node<C,N> > > node;
Node<C,N> nd;
nd.board = B;
nd.prev = -1;
node.push_back(vector<Node<C,N> >(1,nd));
vector<Node<C,N> > v;
for (int i=0; i<10000; i++)
{
if (i%1000==0)
cerr<<i<<endl;
set<unsigned long long> S;
v.clear();
for (int j=0; j<(int)node[i].size(); j++)
{
Board<C,N> b = node[i][j].board;
for (int m1=0; m1<(int)move1.size(); m1++)
{
Node<C,N> n;
n.board = b;
n.board.move(move1[m1]);
if (n.board.hash == b.hash)
continue;
n.prev = j;
n.move = move1[m1];
n.score = (n.board.score<<9)+256;//+(n.board.hash&0xff);
if (S.count(n.board.hash)==0)
{
S.insert(n.board.hash);
for (int m2=0; m2<(int)move2[m1].size(); m2++)
{
Board<C,N> tmp = n.board;
tmp.move(move2[m1][m2]);
n.score = max(n.score, (tmp.score<<9)/*+int(tmp.hash&0xff)*/);
}
n.score += rand()&0xff;
v.push_back(n);
}
}
}
sort(v.begin(), v.end());
if (v.size()>BW)
v.resize(BW);
node.push_back(v);
}
vector<int> ret(30000);
int p = 0;
for (int i=10000; i>0; i--)
{
ret[i*3-3] = node[i][p].move.pos/N;
ret[i*3-2] = node[i][p].move.pos%N;
ret[i*3-1] = node[i][p].move.dir;
p = node[i][p].prev;
}
for (int i=0; i<10000; i++)
B.move(Move(ret[i*3+0]*N+ret[i*3+1], ret[i*3+2]));
cerr<<"N: "<<N<<endl;
cerr<<"BW: "<<BW<<endl;
cerr<<"C: "<<C<<endl;
cerr<<"Score: "<<B.score<<endl;
cerr<<"Board: "<<endl;
for (int y=0; y<N; y++)
{
for (int x=0; x<N; x++)
cerr << int(B.board[y*N+x]);
cerr << endl;
}
cerr<<"Time: "<<1.*clock()/CLOCKS_PER_SEC<<endl;
return ret;
}
class SquareRemover
{
public:
vector<int> playIt(int colors, vector<string> board, int startSeed)
{
int N = (int)board.size();
if (colors==4 && N== 8) return solve<4, 8>(board, startSeed);
if (colors==4 && N== 9) return solve<4, 9>(board, startSeed);
if (colors==4 && N==10) return solve<4,10>(board, startSeed);
if (colors==4 && N==11) return solve<4,11>(board, startSeed);
if (colors==4 && N==12) return solve<4,12>(board, startSeed);
if (colors==4 && N==13) return solve<4,13>(board, startSeed);
if (colors==4 && N==14) return solve<4,14>(board, startSeed);
if (colors==4 && N==15) return solve<4,15>(board, startSeed);
if (colors==4 && N==16) return solve<4,16>(board, startSeed);
if (colors==5 && N== 8) return solve<5, 8>(board, startSeed);
if (colors==5 && N== 9) return solve<5, 9>(board, startSeed);
if (colors==5 && N==10) return solve<5,10>(board, startSeed);
if (colors==5 && N==11) return solve<5,11>(board, startSeed);
if (colors==5 && N==12) return solve<5,12>(board, startSeed);
if (colors==5 && N==13) return solve<5,13>(board, startSeed);
if (colors==5 && N==14) return solve<5,14>(board, startSeed);
if (colors==5 && N==15) return solve<5,15>(board, startSeed);
if (colors==5 && N==16) return solve<5,16>(board, startSeed);
if (colors==6 && N== 8) return solve<6, 8>(board, startSeed);
if (colors==6 && N== 9) return solve<6, 9>(board, startSeed);
if (colors==6 && N==10) return solve<6,10>(board, startSeed);
if (colors==6 && N==11) return solve<6,11>(board, startSeed);
if (colors==6 && N==12) return solve<6,12>(board, startSeed);
if (colors==6 && N==13) return solve<6,13>(board, startSeed);
if (colors==6 && N==14) return solve<6,14>(board, startSeed);
if (colors==6 && N==15) return solve<6,15>(board, startSeed);
if (colors==6 && N==16) return solve<6,16>(board, startSeed);
return vector<int>();
}
};
#ifdef TOPCODER_LOCAL
int main()
{
int colors; cin>>colors;
int N; cin>>N;
vector<string> board(N);
for (int i=0; i<N; i++)
cin>>board[i];
int startSeed; cin>>startSeed;
SquareRemover SR;
vector<int> ret = SR.playIt(colors, board, startSeed);
for (int i=0; i<30000; i++)
cout<<ret[i]<<endl;
}
/*
4 16
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
1
*/
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment