JOISC 2023 Day4T1

发布时间 2023-03-23 21:25:38作者: zhoukangyang

首先假设我们不知道 \((X,Y)\),提取信息看上去很困难。

因此考虑先钦定若干个位置(这里我取了前 \(3 \times 4\) 的矩阵),我们用这些钦定的位置来区分所有的 \((X,Y)\)。对于剩下的位置,可以用来传递信息。

对于一个 \((X,Y)\) ,这些位置会有一些可以染的集合 \(A_{X,Y}\) 和交互库染的集合 \(B_{X,Y}\)

那么非钦定的位置提供的信息是 \(2^{49-|A_{X,Y}|}\),我们还需要 \(2^{|A_{X,Y}|-6}\) 的信息去记录 \(S\)

也就是说,在所有 \(2^{A_{X,Y}}\) 种染色方案中,选择大小为 \(2^{|A_{X,Y}|-6}\) 的子集进行染色。(在染色时可以把钦定的位置染成集合中的样子)。

然后我们要求任意两种染色可能产生的结果是不交的。

事实上 \(43\) 应该是一个非常紧的界,你的解需要做到完美覆盖 \(2^{12}\) 种状态。

取前 \(3 \times 4\) 的矩阵效果会比较好,因为后面的元素可以从 \(2^{12}\) 种状态中随意选择,比较容易找出一组解。

使用一些随机化算法,发现搜出了一组解!然后就通过了。

(我的随机方法:按照 \(A\) 的大小从大到小排序,取对于集合大小不超过 \(10\) 的直接用字典序最小的,大小大于 \(10\) 的随一个顺序。如果有更加厉害的方法请在评论区留言 /kel)

Anna
#include<bits/stdc++.h>
#include "Anna.h"
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
namespace {
const int N = 10;
bool vis[N][N];
int id[N][N], x[N * N], y[N * N], tp;
int vx[1 << 20], vy[1 << 20], vp[1 << 20];
vi P[N][N], A[N][N], B[N][N];
int inited;
int MP[8][8][1 << 14];
inline void init() {
	if(inited) return ;
	inited = 1;
P[0][0] = vi{2};
P[0][1] = vi{0};
P[0][2] = vi{32};
P[0][3] = vi{8};
P[0][4] = vi{30,31,36,37};
P[0][5] = vi{13,14,15,18};
P[0][6] = vi{26,27,28,29};
P[0][7] = vi{8,10,11,12};
P[1][0] = vi{21};
P[1][1] = vi{19};
P[1][2] = vi{30};
P[1][3] = vi{29};
P[1][4] = vi{117,119,123,125};
P[1][5] = vi{106,107,109,110};
P[1][6] = vi{85,87,93,94};
P[1][7] = vi{55,59,77,78};
P[2][0] = vi{25};
P[2][1] = vi{9};
P[2][2] = vi{24};
P[2][3] = vi{8};
P[2][4] = vi{96,97,100,102};
P[2][5] = vi{56,57,60,63};
P[2][6] = vi{28,31,50,54};
P[2][7] = vi{18,20,22,25};
P[3][0] = vi{341,489,97,304,377,481,505,225};
P[3][1] = vi{194,459,130,288,301,193,483,307};
P[3][2] = vi{382,389,385,387,502,374,312,508};
P[3][3] = vi{232,384,489,77,424,484,193,352};
P[3][4] = vi{2090,1897,2653,3555,3630,2856,3505,2397,3872,2260,3497,3887,1452,2085,835,3797,53,2340,2128,3717,2488,717,3948,1097,1142,2396,3704,1158,1346,1750,3818,1011,3920,3945,2597,1686,3613,1532,1862,3221,3645,3752,640,3677,2035,2972,1033,2392,1096,2934,2792,1506,695,703,3375,1446,3450,3623,737,2231,1929,2862,1884,3507};
P[3][5] = vi{1088,2460,2719,4037,3398,888,667,2642,714,3466,1640,3465,2994,2964,3726,3306,2706,2644,3446,3234,2172,1948,3667,3807,2850,2376,3307,3706,1780,2551,2275,2599,1188,1876,2143,1248,3552,158,650,2196,844,704,3842,725,2525,403,2598,4009,1926,634,3338,2363,913,3154,2342,1423,946,1436,539,2411,1231,3709,2761,729};
P[3][6] = vi{3829,1132,3614,3923,2137,3299,3339,2281,2341,743,1583,1012,2921,2426,3158,2339,282,712,2919,3205,1538,1570,3408,1916,3786,2819,4052,3809,924,2399,2556,2103,2351,2089,2830,1206,619,697,375,1151,414,2204,3670,2130,3866,2982,4053,759,1503,3571,3276,2922,639,993,3330,3765,1794,2412,2680,3222,3756,3538,3407,630};
P[3][7] = vi{2430,1871,3210,3522,632,1660,2393,1974,4064,3539,1951,2365,2379,1032,1516,2763,3598,3323,3266,1880,3855,2357,1177,3596,1266,2283,3423,3719,3357,2593,1007,1256,1364,2537,3766,886,1071,3406,3451,2920,648,734,2636,1804,800,847,2452,59,1218,2632,2771,2509,2848,2980,1388,2081,1510,2939,2777,3265,1368,3962,1442,1190};
P[4][0] = vi{437,422,333,417,471,507,161,499};
P[4][1] = vi{429,129,293,491,418,475,395,467};
P[4][2] = vi{487,186,430,444,503,242,375,314};
P[4][3] = vi{441,209,428,377,224,141,196,361};
P[4][4] = vi{357,2871,3434,3702,716,649,2811,2087,3902,3300,156,118,3233,1839,1110,1730,665,2852,286,663,1711,1491,762,2239,2350,3817,2784,3707,3207,2008,1350,698,1254,1106,3791,3541,2422,3751,1999,1321,653,3958,3556,2270,2594,1681,1972,1272,2140,1234,1183,3395,2031,692,621,1692,2462,1464,2466,1363,30,3010,670,1919};
P[4][5] = vi{3816,959,2755,2533,3880,686,3108,155,1314,3965,146,535,2255,3949,1455,27,3296,767,2520,2738,2760,571,2663,2380,2385,1172,1935,1257,2372,2806,2337,771,1400,3178,4093,1872,1295,2347,3513,2510,726,2047,2860,1601,4025,1129,1156,3853,1910,311,3179,3304,2082,2794,3410,651,2084,2012,1200,2020,2264,1459,850,2141};
P[4][6] = vi{3476,2969,3573,3759,2086,2455,1001,944,3471,2768,921,2628,3490,3403,3214,1148,2428,803,3558,3297,710,655,2568,1921,3273,3969,757,1676,2159,1169,2622,3478,3467,1512,3263,1279,1670,2194,2640,1576,542,1372,1878,1202,804,3523,3850,2822,2685,2459,113,2742,2529,3734,1668,2472,2003,2595,3412,3272,1475,755,1216,2131};
P[4][7] = vi{3964,1014,730,383,2458,147,3026,2882,2596,3113,1990,2349,2795,401,3849,1267,1535,1912,3837,1433,2207,2369,2678,1465,950,4077,3713,2262,2846,3487,2935,1010,719,1528,2229,2772,673,3190,948,2493,3690,2710,1404,2753,3749,3311,2362,538,731,749,2769,3619,2017,947,1441,2978,3310,1204,2161,727,1924,2395,2947,3167};
P[5][0] = vi{351,305,439,497,325,415,309,232};
P[5][1] = vi{482,292,319,306,449,310,248,290};
P[5][2] = vi{244,318,270,178,376,386,494,212};
P[5][3] = vi{272,233,320,249,296,225,420,185};
P[5][4] = vi{3192,2516,3744,1268,3722,1362,2754,657,3420,3264,4068,3932,3761,3553,2564,3735,1263,2371,1474,3790,2863,2382,127,1937,2508,3389,995,3416,2407,2615,3767,2327,3820,806,2384,2202,1801,3194,675,150,2504,1695,153,2232,1656,2272,1247,3685,2282,3282,735,2345,3617,3390,863,770,2417,902,635,3946,1225,751,715,745};
P[5][5] = vi{3470,3924,1654,3163,774,3754,2373,2716,3808,2552,2236,2966,154,3327,3631,2075,26,2136,3231,2280,4060,2265,3020,2560,616,2624,3255,3249,2390,2574,3030,2285,3176,3540,1270,314,2025,2088,3773,3402,975,2019,1203,966,1128,3433,2387,3595,2383,2473,1647,3317,2414,2797,2470,2389,1208,3554,671,1456,2092,567,3421,3491};
P[5][6] = vi{2427,851,732,2156,2071,2248,1956,1478,126,1663,2505,2855,1100,1201,2575,2540,3881,4013,3576,1568,2454,2892,992,617,3805,1887,574,1091,145,3217,3933,3548,836,1622,2976,2199,2331,4000,4065,23,3489,1384,2268,2151,2999,119,1776,1631,1024,2106,991,2170,2346,151,3789,815,613,3285,4017,3099,3525,3988,720,4001};
P[5][7] = vi{631,2899,4061,1375,2094,3117,1167,3298,652,2951,1734,2521,315,945,2296,2091,3394,1737,3283,1577,2457,1164,3165,1094,2413,677,2391,2132,2886,1103,1119,1684,739,750,3646,2344,3610,2375,783,3785,3235,1471,736,283,4056,2501,1260,2590,3775,724,3874,2487,718,1955,2166,3910,2983,3226,3119,58,3812,2287,2157,1196};
P[6][0] = vi{469,284,479,343,397,113,430,414};
P[6][1] = vi{315,421,450,289,297,370,177,250};
P[6][2] = vi{486,188,511,383,440,404,378,510};
P[6][3] = vi{336,353,356,416,505,192,313,157};
P[6][4] = vi{1615,3757,2469,2464,713,3611,2524,879,996,3063,3622,3355,1967,3733,3107,3419,2752,1449,3239,2839,3215,3906,2348,3867,317,3588,2878,1209,2606,3821,1135,2477,2492,3106,687,3200,3599,1398,3411,159,1833,103,2708,1507,1407,1036,2468,2527,2940,3729,61,3373,2547,2101,3247,3481,1987,1705,1420,2374,1468,3242,411,2173};
P[6][5] = vi{1961,3303,615,2780,1945,802,2291,1551,2793,3618,3823,1391,3549,2503,101,1425,2465,1359,117,1412,404,3337,2489,3594,931,3049,892,3977,1487,359,1414,1023,928,3201,2366,2338,2336,2607,2368,2818,3781,2902,1224,3230,854,3305,2545,3301,1161,2249,2471,756,2998,3362,3177,3457,2799,3839,415,1807,1775,918,3787,1986};
P[6][6] = vi{3011,3901,1439,2511,3985,676,2667,1977,3743,2174,2297,3256,629,1545,1727,2016,2405,1458,1220,1090,1180,3758,3822,382,681,2743,3015,2431,2541,705,1826,2421,2526,2370,1665,4022,2158,2557,3134,1746,3851,873,638,2080,366,3105,644,2641,1779,2467,2300,1760,1505,1743,2776,1238,3293,647,3118,1193,2381,645,2765,3111};
P[6][7] = vi{3268,2015,3885,2666,3267,1152,682,1824,1428,699,3560,3473,279,2095,3835,318,1068,765,3448,1235,2518,3319,2206,3813,834,1187,1609,1673,3341,2898,3621,3691,3251,838,728,1360,2553,1347,1508,1276,3031,2237,1039,406,679,1759,2887,367,3963,1699,654,2583,1513,3561,3173,570,2962,3486,2175,1606,3116,3544,2423,1228};
P[7][0] = vi{30,446,461,28,29,209,435,486};
P[7][1] = vi{291,294,454,451,295,283,361,411};
P[7][2] = vi{405,180,334,495,446,504,500,252};
P[7][3] = vi{448,13,297,300,425,481,236,480};
P[7][4] = vi{410,2751,691,2652,2343,733,55,1324,1282,1700,3990,916,3869,3616,3133,740,1409,2388,1721,3110,2386,3708,3062,1460,2924,3320,369,2592,3926,2549,148,1327,4085,2648,1250,1769,3315,2661,1443,1065,2774,1641,3687,2528,3907,646,3040,3155,1932,1548,1444,3666,3993,2938,2377,2299,2946,964,1252,721,953,709,4029,2536};
P[7][5] = vi{2485,111,1008,2683,662,2851,2535,2572,2109,1160,3302,3041,3109,1689,618,2378,4045,688,2274,2823,3960,1144,1971,1292,2429,2950,2155,3727,943,641,3803,2519,2767,407,752,1174,668,2643,3405,309,3047,1430,1186,1940,3414,2198,3369,689,1715,3483,2410,2682,1199,1089,2154,2711,2967,2903,3732,402,1215,982,1500,683};
P[7][6] = vi{2936,2415,3195,927,3947,3175,2979,3777,2171,1747,1457,2289,1644,3269,766,895,3512,2359,1716,3432,2129,620,763,636,1153,685,623,2779,2517,1523,1366,3922,3559,1462,1289,2762,3237,412,2854,2110,1504,2149,708,409,2883,2646,1679,2107,1519,972,3253,3208,1496,2134,3557,660,2253,3536,1222,911,4069,110,2884,3575};
P[7][7] = vi{3745,2139,637,3220,3001,1212,2530,3917,1580,2476,4048,1417,1764,3246,2083,3944,3101,711,1058,741,622,2831,702,1903,1092,3928,3482,3870,1264,2463,2684,2450,2785,373,2531,3223,3027,1385,3533,746,4073,2649,1185,1942,1791,1983,2093,3343,1026,3435,666,3620,2923,374,2273,1107,672,2770,62,747,3277,1970,3819,932};
	me(id, -1);
	L(i, 0, 2) 
		L(j, 0, 3) 
			vis[i][j] = true;
	L(i, 0, 7) 
		L(j, 0, 7) 
			if(vis[i][j]) 
				id[i][j] = tp, x[tp] = i, y[tp] = j, ++tp; 
	L(x, 0, 7) L(y, 0, 7) {
		L(i, 0, 7) {
			L(j, 0, 7) 
				if(x == i || y == j) {
					if(vis[i][j]) {
						B[x][y].emplace_back(id[i][j]);
					}
				} else {
					if(vis[i][j]) {
						A[x][y].emplace_back(id[i][j]);
					}
				}
		}
		int cnt = 0;
		for(auto i : P[x][y]) {
			int kan = 0;
			L(j, 0, sz(A[x][y]) - 1) 
				if(i >> j & 1) 
					kan += 1 << A[x][y][j];
			L(t, 0, (1 << sz(B[x][y])) - 1) {
				int s = kan;
				L(j, 0, sz(B[x][y]) - 1) 
					if(t >> j & 1)
						s += 1 << B[x][y][j];
				vx[s] = x, vy[s] = y, vp[s] = cnt;	
			}
			MP[x][y][cnt] = kan;
			++cnt;
		}
	}
}
}

void Anna(int X, int Y, int N, std::string S) {
	init();
	unsigned long long val = 0;
	L(i, 0, N - 1) 
		val <<= 1, val += S[i] - 'A';
//	cerr<<"val="<<val<<endl;
	int len = sz(A[X][Y]) - 6;
	int kan = MP[X][Y][val & ((1 << len) - 1)];
	val >>= len;
	
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) if(i != X && j != Y) {
			if (!vis[i][j]) {
				Paint(i, j, val & 1), val >>= 1;
			} else {
				Paint(i, j, kan >> id[i][j] & 1);
			}
		}
	}
}
Bruno
#include<bits/stdc++.h>
#include "Bruno.h"
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
namespace {
const int N = 10;
bool vis[N][N];
int id[N][N], x[N * N], y[N * N], tp;
int vx[1 << 20], vy[1 << 20], vp[1 << 20];
vi P[N][N], A[N][N], B[N][N];
int inited;
int MP[8][8][1 << 14];
inline void init() {
	if(inited) return ;
	inited = 1;
P[0][0] = vi{2};
P[0][1] = vi{0};
P[0][2] = vi{32};
P[0][3] = vi{8};
P[0][4] = vi{30,31,36,37};
P[0][5] = vi{13,14,15,18};
P[0][6] = vi{26,27,28,29};
P[0][7] = vi{8,10,11,12};
P[1][0] = vi{21};
P[1][1] = vi{19};
P[1][2] = vi{30};
P[1][3] = vi{29};
P[1][4] = vi{117,119,123,125};
P[1][5] = vi{106,107,109,110};
P[1][6] = vi{85,87,93,94};
P[1][7] = vi{55,59,77,78};
P[2][0] = vi{25};
P[2][1] = vi{9};
P[2][2] = vi{24};
P[2][3] = vi{8};
P[2][4] = vi{96,97,100,102};
P[2][5] = vi{56,57,60,63};
P[2][6] = vi{28,31,50,54};
P[2][7] = vi{18,20,22,25};
P[3][0] = vi{341,489,97,304,377,481,505,225};
P[3][1] = vi{194,459,130,288,301,193,483,307};
P[3][2] = vi{382,389,385,387,502,374,312,508};
P[3][3] = vi{232,384,489,77,424,484,193,352};
P[3][4] = vi{2090,1897,2653,3555,3630,2856,3505,2397,3872,2260,3497,3887,1452,2085,835,3797,53,2340,2128,3717,2488,717,3948,1097,1142,2396,3704,1158,1346,1750,3818,1011,3920,3945,2597,1686,3613,1532,1862,3221,3645,3752,640,3677,2035,2972,1033,2392,1096,2934,2792,1506,695,703,3375,1446,3450,3623,737,2231,1929,2862,1884,3507};
P[3][5] = vi{1088,2460,2719,4037,3398,888,667,2642,714,3466,1640,3465,2994,2964,3726,3306,2706,2644,3446,3234,2172,1948,3667,3807,2850,2376,3307,3706,1780,2551,2275,2599,1188,1876,2143,1248,3552,158,650,2196,844,704,3842,725,2525,403,2598,4009,1926,634,3338,2363,913,3154,2342,1423,946,1436,539,2411,1231,3709,2761,729};
P[3][6] = vi{3829,1132,3614,3923,2137,3299,3339,2281,2341,743,1583,1012,2921,2426,3158,2339,282,712,2919,3205,1538,1570,3408,1916,3786,2819,4052,3809,924,2399,2556,2103,2351,2089,2830,1206,619,697,375,1151,414,2204,3670,2130,3866,2982,4053,759,1503,3571,3276,2922,639,993,3330,3765,1794,2412,2680,3222,3756,3538,3407,630};
P[3][7] = vi{2430,1871,3210,3522,632,1660,2393,1974,4064,3539,1951,2365,2379,1032,1516,2763,3598,3323,3266,1880,3855,2357,1177,3596,1266,2283,3423,3719,3357,2593,1007,1256,1364,2537,3766,886,1071,3406,3451,2920,648,734,2636,1804,800,847,2452,59,1218,2632,2771,2509,2848,2980,1388,2081,1510,2939,2777,3265,1368,3962,1442,1190};
P[4][0] = vi{437,422,333,417,471,507,161,499};
P[4][1] = vi{429,129,293,491,418,475,395,467};
P[4][2] = vi{487,186,430,444,503,242,375,314};
P[4][3] = vi{441,209,428,377,224,141,196,361};
P[4][4] = vi{357,2871,3434,3702,716,649,2811,2087,3902,3300,156,118,3233,1839,1110,1730,665,2852,286,663,1711,1491,762,2239,2350,3817,2784,3707,3207,2008,1350,698,1254,1106,3791,3541,2422,3751,1999,1321,653,3958,3556,2270,2594,1681,1972,1272,2140,1234,1183,3395,2031,692,621,1692,2462,1464,2466,1363,30,3010,670,1919};
P[4][5] = vi{3816,959,2755,2533,3880,686,3108,155,1314,3965,146,535,2255,3949,1455,27,3296,767,2520,2738,2760,571,2663,2380,2385,1172,1935,1257,2372,2806,2337,771,1400,3178,4093,1872,1295,2347,3513,2510,726,2047,2860,1601,4025,1129,1156,3853,1910,311,3179,3304,2082,2794,3410,651,2084,2012,1200,2020,2264,1459,850,2141};
P[4][6] = vi{3476,2969,3573,3759,2086,2455,1001,944,3471,2768,921,2628,3490,3403,3214,1148,2428,803,3558,3297,710,655,2568,1921,3273,3969,757,1676,2159,1169,2622,3478,3467,1512,3263,1279,1670,2194,2640,1576,542,1372,1878,1202,804,3523,3850,2822,2685,2459,113,2742,2529,3734,1668,2472,2003,2595,3412,3272,1475,755,1216,2131};
P[4][7] = vi{3964,1014,730,383,2458,147,3026,2882,2596,3113,1990,2349,2795,401,3849,1267,1535,1912,3837,1433,2207,2369,2678,1465,950,4077,3713,2262,2846,3487,2935,1010,719,1528,2229,2772,673,3190,948,2493,3690,2710,1404,2753,3749,3311,2362,538,731,749,2769,3619,2017,947,1441,2978,3310,1204,2161,727,1924,2395,2947,3167};
P[5][0] = vi{351,305,439,497,325,415,309,232};
P[5][1] = vi{482,292,319,306,449,310,248,290};
P[5][2] = vi{244,318,270,178,376,386,494,212};
P[5][3] = vi{272,233,320,249,296,225,420,185};
P[5][4] = vi{3192,2516,3744,1268,3722,1362,2754,657,3420,3264,4068,3932,3761,3553,2564,3735,1263,2371,1474,3790,2863,2382,127,1937,2508,3389,995,3416,2407,2615,3767,2327,3820,806,2384,2202,1801,3194,675,150,2504,1695,153,2232,1656,2272,1247,3685,2282,3282,735,2345,3617,3390,863,770,2417,902,635,3946,1225,751,715,745};
P[5][5] = vi{3470,3924,1654,3163,774,3754,2373,2716,3808,2552,2236,2966,154,3327,3631,2075,26,2136,3231,2280,4060,2265,3020,2560,616,2624,3255,3249,2390,2574,3030,2285,3176,3540,1270,314,2025,2088,3773,3402,975,2019,1203,966,1128,3433,2387,3595,2383,2473,1647,3317,2414,2797,2470,2389,1208,3554,671,1456,2092,567,3421,3491};
P[5][6] = vi{2427,851,732,2156,2071,2248,1956,1478,126,1663,2505,2855,1100,1201,2575,2540,3881,4013,3576,1568,2454,2892,992,617,3805,1887,574,1091,145,3217,3933,3548,836,1622,2976,2199,2331,4000,4065,23,3489,1384,2268,2151,2999,119,1776,1631,1024,2106,991,2170,2346,151,3789,815,613,3285,4017,3099,3525,3988,720,4001};
P[5][7] = vi{631,2899,4061,1375,2094,3117,1167,3298,652,2951,1734,2521,315,945,2296,2091,3394,1737,3283,1577,2457,1164,3165,1094,2413,677,2391,2132,2886,1103,1119,1684,739,750,3646,2344,3610,2375,783,3785,3235,1471,736,283,4056,2501,1260,2590,3775,724,3874,2487,718,1955,2166,3910,2983,3226,3119,58,3812,2287,2157,1196};
P[6][0] = vi{469,284,479,343,397,113,430,414};
P[6][1] = vi{315,421,450,289,297,370,177,250};
P[6][2] = vi{486,188,511,383,440,404,378,510};
P[6][3] = vi{336,353,356,416,505,192,313,157};
P[6][4] = vi{1615,3757,2469,2464,713,3611,2524,879,996,3063,3622,3355,1967,3733,3107,3419,2752,1449,3239,2839,3215,3906,2348,3867,317,3588,2878,1209,2606,3821,1135,2477,2492,3106,687,3200,3599,1398,3411,159,1833,103,2708,1507,1407,1036,2468,2527,2940,3729,61,3373,2547,2101,3247,3481,1987,1705,1420,2374,1468,3242,411,2173};
P[6][5] = vi{1961,3303,615,2780,1945,802,2291,1551,2793,3618,3823,1391,3549,2503,101,1425,2465,1359,117,1412,404,3337,2489,3594,931,3049,892,3977,1487,359,1414,1023,928,3201,2366,2338,2336,2607,2368,2818,3781,2902,1224,3230,854,3305,2545,3301,1161,2249,2471,756,2998,3362,3177,3457,2799,3839,415,1807,1775,918,3787,1986};
P[6][6] = vi{3011,3901,1439,2511,3985,676,2667,1977,3743,2174,2297,3256,629,1545,1727,2016,2405,1458,1220,1090,1180,3758,3822,382,681,2743,3015,2431,2541,705,1826,2421,2526,2370,1665,4022,2158,2557,3134,1746,3851,873,638,2080,366,3105,644,2641,1779,2467,2300,1760,1505,1743,2776,1238,3293,647,3118,1193,2381,645,2765,3111};
P[6][7] = vi{3268,2015,3885,2666,3267,1152,682,1824,1428,699,3560,3473,279,2095,3835,318,1068,765,3448,1235,2518,3319,2206,3813,834,1187,1609,1673,3341,2898,3621,3691,3251,838,728,1360,2553,1347,1508,1276,3031,2237,1039,406,679,1759,2887,367,3963,1699,654,2583,1513,3561,3173,570,2962,3486,2175,1606,3116,3544,2423,1228};
P[7][0] = vi{30,446,461,28,29,209,435,486};
P[7][1] = vi{291,294,454,451,295,283,361,411};
P[7][2] = vi{405,180,334,495,446,504,500,252};
P[7][3] = vi{448,13,297,300,425,481,236,480};
P[7][4] = vi{410,2751,691,2652,2343,733,55,1324,1282,1700,3990,916,3869,3616,3133,740,1409,2388,1721,3110,2386,3708,3062,1460,2924,3320,369,2592,3926,2549,148,1327,4085,2648,1250,1769,3315,2661,1443,1065,2774,1641,3687,2528,3907,646,3040,3155,1932,1548,1444,3666,3993,2938,2377,2299,2946,964,1252,721,953,709,4029,2536};
P[7][5] = vi{2485,111,1008,2683,662,2851,2535,2572,2109,1160,3302,3041,3109,1689,618,2378,4045,688,2274,2823,3960,1144,1971,1292,2429,2950,2155,3727,943,641,3803,2519,2767,407,752,1174,668,2643,3405,309,3047,1430,1186,1940,3414,2198,3369,689,1715,3483,2410,2682,1199,1089,2154,2711,2967,2903,3732,402,1215,982,1500,683};
P[7][6] = vi{2936,2415,3195,927,3947,3175,2979,3777,2171,1747,1457,2289,1644,3269,766,895,3512,2359,1716,3432,2129,620,763,636,1153,685,623,2779,2517,1523,1366,3922,3559,1462,1289,2762,3237,412,2854,2110,1504,2149,708,409,2883,2646,1679,2107,1519,972,3253,3208,1496,2134,3557,660,2253,3536,1222,911,4069,110,2884,3575};
P[7][7] = vi{3745,2139,637,3220,3001,1212,2530,3917,1580,2476,4048,1417,1764,3246,2083,3944,3101,711,1058,741,622,2831,702,1903,1092,3928,3482,3870,1264,2463,2684,2450,2785,373,2531,3223,3027,1385,3533,746,4073,2649,1185,1942,1791,1983,2093,3343,1026,3435,666,3620,2923,374,2273,1107,672,2770,62,747,3277,1970,3819,932};
	me(id, -1);
	L(i, 0, 2) 
		L(j, 0, 3) 
			vis[i][j] = true;
	L(i, 0, 7) 
		L(j, 0, 7) 
			if(vis[i][j]) 
				id[i][j] = tp, x[tp] = i, y[tp] = j, ++tp; 
	L(x, 0, 7) L(y, 0, 7) {
		L(i, 0, 7) {
			L(j, 0, 7) 
				if(x == i || y == j) {
					if(vis[i][j]) {
						B[x][y].emplace_back(id[i][j]);
					}
				} else {
					if(vis[i][j]) {
						A[x][y].emplace_back(id[i][j]);
					}
				}
		}
		int cnt = 0;
		for(auto i : P[x][y]) {
			int kan = 0;
			L(j, 0, sz(A[x][y]) - 1) 
				if(i >> j & 1) 
					kan += 1 << A[x][y][j];
			L(t, 0, (1 << sz(B[x][y])) - 1) {
				int s = kan;
				L(j, 0, sz(B[x][y]) - 1) 
					if(t >> j & 1)
						s += 1 << B[x][y][j];
				vx[s] = x, vy[s] = y, vp[s] = cnt;	
			}
			MP[x][y][cnt] = kan;
			++cnt;
		}
	}
}
}

std::string Bruno(int N, std::vector<std::vector<int>> T) {
	init();
	int s = 0;
	L(i, 0, 7) 
		L(j, 0, 7) 
			if(vis[i][j]) 
				s += T[i][j] << id[i][j];
	int X = vx[s], Y = vy[s], kan = vp[s];
	int len = sz(A[X][Y]) - 6;
//	cerr << X << ' ' << Y << endl;
	
	unsigned long long val = 0;
	R(i, 7, 0) {
		R(j, 7, 0) if(i != X && j != Y) {
			if(!vis[i][j]) {
				val <<= 1, val += T[i][j];
			} 
		}
	}
	val <<= len, val += kan; 
	
	string S;
	S.resize(N);
	R(i, N - 1, 0) 
		S[i] = (val & 1) + 'A', val >>= 1;
	return S;
} len = sz(A[X][Y]) - 6;
	int kan = MP[X][Y][val & ((1 << len) - 1)];
	val >>= len;
	
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) if(i != X && j != Y) {
			if (!vis[i][j]) {
				Paint(i, j, val & 1), val >>= 1;
			} else {
				Paint(i, j, kan >> id[i][j] & 1);
			}
		}
	}
}