API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
110
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 21.97 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. int n, w, m;
  6. bool LOCAL = false;
  7. void check(vector < string >& s) {
  8. assert(s.size() == n);
  9. for (int i = 0; i < n; i++) {
  10. for (int j = i + 1; j < n; j++) {
  11. int cnt = 0;
  12. assert(s[i].size() == s[j].size());
  13. for (int k = 0; k < s[i].size(); k++) {
  14. cnt += (s[i][k] != s[j][k]);
  15. }
  16. assert(cnt >= w);
  17. }
  18. }
  19. }
  20. void printAns(vector < string >& s) {
  21. if (LOCAL) {
  22. check(s);
  23. }
  24. cout << s[0].size() << '\n';
  25. for (int i = 0; i < s[0].size(); i++) {
  26. for (int j = 0; j < n; j++) {
  27. cout << s[j][i];
  28. }
  29. cout << '\n';
  30. }
  31. }
  32. const int maxN = (1 << 12) + 20;
  33. string bin[maxN][15];
  34. int lg[maxN];
  35. vector < int > f8 = {3, 4, 6, 1, 0, 7, 5, 2};
  36. vector < int > f16 = {1, 6, 10, 15, 14, 11, 9, 5, 13, 3, 0, 12, 4, 8, 7, 2};
  37. vector < int > f32 = {4, 22, 28, 1, 8, 17, 18, 14, 21, 7, 2, 25, 26, 31, 5, 11, 3, 0, 10, 30, 20, 6, 13, 23, 15, 19, 27, 16, 9, 12, 24, 29};
  38. vector < vector < int > > gg8 = {{1, 7, 4, 5, 6, 0, 3, 2}
  39. ,
  40. {7, 4, 5, 2, 3, 1, 0, 6}
  41. ,
  42. {6, 4, 3, 7, 1, 0, 5, 2}
  43. ,
  44. {4, 2, 5, 0, 6, 1, 7, 3}
  45. ,
  46. {4, 5, 7, 3, 1, 0, 2, 6}
  47. };
  48. vector < vector < int > > gg16 = {{9, 10, 8, 11, 12, 1, 15, 4, 0, 2, 6, 7, 3, 5, 13, 14}
  49. ,
  50. {13, 15, 8, 1, 4, 0, 6, 2, 12, 11, 9, 14, 5, 10, 7, 3}
  51. ,
  52. {9, 14, 3, 12, 7, 15, 1, 8, 11, 2, 5, 4, 6, 13, 10, 0}
  53. ,
  54. {4, 1, 5, 10, 0, 12, 13, 2, 8, 15, 9, 6, 14, 7, 11, 3}
  55. ,
  56. {9, 5, 15, 12, 1, 10, 14, 3, 4, 11, 6, 0, 7, 13, 2, 8}
  57. };
  58. vector < vector < int > > gg32 = {{7, 18, 27, 13, 17, 16, 14, 20, 25, 10, 30, 2, 31, 23, 0, 5, 28, 11, 29, 1, 8, 9, 3, 26, 4, 22, 21, 6, 15, 12, 24, 19}
  59. ,
  60. {21, 30, 25, 1, 11, 12, 20, 22, 5, 13, 0, 6, 26, 10, 28, 14, 23, 27, 19, 9, 15, 24, 17, 3, 31, 18, 4, 2, 8, 29, 16, 7}
  61. ,
  62. {5, 4, 6, 31, 23, 7, 16, 13, 12, 20, 11, 24, 26, 29, 14, 3, 1, 27, 15, 17, 9, 25, 0, 22, 18, 21, 8, 28, 30, 10, 2, 19}
  63. ,
  64. {20, 15, 11, 30, 18, 9, 2, 12, 29, 31, 23, 16, 21, 26, 7, 27, 25, 14, 24, 4, 28, 3, 10, 19, 8, 1, 22, 6, 13, 17, 0, 5}
  65. ,
  66. {20, 0, 9, 25, 16, 13, 17, 3, 28, 18, 10, 2, 30, 23, 24, 11, 31, 22, 1, 14, 26, 27, 19, 29, 4, 21, 5, 8, 12, 7, 15, 6}
  67. };
  68. vector < string > s(n);
  69. vector < vector < int > > best32 = {{0, 3, 17, 28, 16, 5, 19, 6, 24, 4, 13, 15, 31, 11, 14, 8, 10, 30, 21, 1, 12, 2, 25, 9, 18, 22, 20, 29, 23, 26, 7, 27}
  70. ,
  71. {23, 27, 28, 9, 14, 2, 18, 24, 19, 30, 13, 25, 7, 3, 0, 20, 6, 17, 12, 16, 8, 29, 4, 1, 22, 5, 31, 15, 11, 10, 26, 21}
  72. ,
  73. {11, 26, 24, 4, 12, 15, 19, 3, 31, 22, 16, 5, 18, 17, 25, 8, 13, 1, 14, 29, 0, 7, 23, 30, 20, 28, 27, 21, 2, 6, 10, 9}
  74. ,
  75. {0, 1, 26, 9, 30, 21, 31, 12, 6, 24, 15, 29, 17, 28, 18, 7, 13, 5, 27, 2, 22, 19, 4, 14, 20, 25, 3, 11, 16, 23, 8, 10}
  76. ,
  77. {9, 0, 17, 8, 15, 14, 3, 27, 7, 12, 30, 26, 21, 19, 10, 28, 2, 22, 11, 24, 31, 20, 25, 18, 1, 4, 23, 16, 6, 5, 29, 13}
  78. ,
  79. {2, 16, 10, 29, 12, 8, 23, 15, 26, 21, 24, 6, 18, 4, 20, 11, 13, 25, 22, 1, 7, 5, 31, 3, 28, 14, 30, 19, 27, 17, 0, 9}
  80. ,
  81. {15, 2, 8, 11, 17, 9, 22, 16, 19, 6, 31, 29, 25, 3, 26, 23, 4, 7, 30, 27, 10, 21, 1, 14, 5, 18, 13, 12, 20, 24, 28, 0}
  82. };
  83. vector < vector < int > > best64 = {{56, 59, 63, 4, 37, 43, 38, 10, 1, 26, 11, 35, 34, 0, 49, 16, 23, 17, 7, 13, 9, 8, 40, 46, 57, 52, 47, 15, 31, 45, 24, 39, 55, 53, 51, 41, 50, 5, 60, 54, 32, 20, 48, 62, 36, 42, 12, 30, 33, 21, 22, 6, 61, 3, 28, 18, 19, 29, 44, 14, 27, 25, 58, 2}
  84. ,
  85. {18, 40, 37, 16, 15, 29, 58, 50, 27, 36, 57, 4, 20, 26, 45, 55, 48, 38, 7, 47, 56, 17, 2, 6, 41, 30, 10, 21, 14, 43, 32, 13, 63, 46, 54, 35, 28, 1, 34, 23, 0, 11, 49, 44, 5, 19, 25, 60, 62, 51, 3, 31, 22, 39, 8, 12, 59, 33, 42, 53, 24, 9, 61, 52}
  86. ,
  87. {20, 29, 38, 11, 36, 22, 54, 53, 35, 42, 61, 45, 13, 52, 26, 63, 25, 57, 62, 12, 16, 17, 3, 41, 32, 50, 5, 7, 18, 0, 39, 30, 28, 1, 47, 21, 55, 56, 27, 48, 24, 10, 8, 15, 60, 9, 6, 49, 14, 23, 34, 31, 46, 4, 33, 40, 58, 44, 43, 59, 2, 51, 37, 19}
  88. ,
  89. {58, 35, 26, 48, 62, 12, 43, 61, 8, 42, 31, 6, 47, 18, 44, 54, 49, 33, 46, 28, 1, 27, 4, 34, 5, 38, 59, 29, 11, 7, 23, 0, 9, 41, 40, 24, 63, 19, 17, 2, 56, 51, 45, 53, 14, 10, 3, 16, 22, 13, 20, 21, 30, 15, 32, 50, 25, 37, 57, 55, 52, 39, 60, 36}
  90. ,
  91. {17, 18, 61, 57, 33, 44, 45, 46, 58, 22, 3, 6, 48, 35, 4, 47, 39, 41, 0, 36, 40, 55, 53, 54, 49, 11, 26, 59, 25, 2, 31, 43, 7, 16, 1, 38, 21, 14, 60, 42, 34, 27, 24, 20, 29, 30, 15, 37, 9, 56, 51, 19, 12, 23, 5, 32, 8, 63, 50, 52, 28, 62, 13, 10}
  92. ,
  93. {27, 47, 15, 17, 5, 38, 50, 16, 39, 62, 56, 42, 28, 1, 61, 32, 60, 6, 48, 11, 2, 40, 53, 23, 30, 26, 34, 35, 31, 7, 44, 45, 12, 4, 41, 63, 54, 51, 43, 13, 22, 55, 18, 10, 19, 59, 57, 3, 9, 20, 0, 8, 58, 46, 52, 33, 24, 49, 37, 25, 14, 21, 29, 36}
  94. };
  95. pair < vector < int >, bool > can(int x, vector < int > trans) {
  96. vector < int > f(trans.size());
  97. vector < bool > ok(x + 1);
  98. vector < int > prv(x + 1);
  99. prv[0] = -1;
  100. ok[0] = true;
  101. for (int i = 0; i < trans.size(); i++) {
  102. for (int j = 0; j + trans[i] <= x; j++) {
  103. if (ok[j]) {
  104. ok[j + trans[i]] = true;
  105. prv[j + trans[i]] = i;
  106. }
  107. }
  108. }
  109. if (!ok[x]) return make_pair(vector < int >(), false);
  110. while (x > 0) {
  111. f[prv[x]]++;
  112. x -= trans[prv[x]];
  113. }
  114. return make_pair(f, true);
  115. }
  116. vector < vector < int > > optAnses[10][10];
  117. int vals[10][10];
  118. void solve(int n, int w) {
  119. if (w < 0) return ;
  120. int lim = (1 << lg[n]);
  121. if (lim == 2 || w == 1) {
  122. for (int i = 0; i < n; i++) {
  123. for (int j = 0; j < w; j++) {
  124. s[i] += bin[i][lg[n]];
  125. }
  126. }
  127. return ;
  128. }
  129. if (lim == 4) {
  130. int k = w / 4;
  131. for (int i = 0; i < n; i++) {
  132. for (int j = 0; j < k; j++) {
  133. if (i == 0) {
  134. for (int t = 0; t < 3; t++) {
  135. s[i] += bin[0][lg[4]];
  136. }
  137. }
  138. else {
  139. for (int t = 0; t < 3; t++) {
  140. s[i] += bin[(i + t) % 3 + 1][lg[4]];
  141. }
  142. }
  143. }
  144. }
  145. int res = w % 4;
  146. for (int i = 0; i < n; i++) {
  147. for (int j = 0; j < res; j++) {
  148. s[i] += bin[i][lg[4]];
  149. }
  150. }
  151. return ;
  152. }
  153. else {
  154. int c1 = -1;
  155. int c2 = -1;
  156. int c3 = -1;
  157. int k = lg[n];
  158. int to = -1;
  159. ld bestRat = -1;
  160. int optLen = -1;
  161. for (int len = 6; len <= 7; len++) {
  162. for (int i = 6; i >= 3; i--) {
  163. vector < int > trans;
  164. int mn = 10000;
  165. for (int j = i; j <= 6; j++) {
  166. trans.push_back(j);
  167. mn = min(mn, vals[len][j]);
  168. }
  169. auto tt = can(k, trans);
  170. if (!tt.second) continue;
  171. if (bestRat < (1.0 * mn / len)) {
  172. bestRat = (ld)mn / len;
  173. optLen = len;
  174. to = i;
  175. }
  176. }
  177. }
  178. if (w >= vals[optLen][to]) {
  179. assert(to != -1);
  180. vector < int > trans;
  181. for (int j = to; j <= 6; j++) {
  182. trans.push_back(j);
  183. }
  184. auto tt = can(k, trans);
  185. assert(tt.second);
  186. for (int j = 0; j < n; j++) {
  187. int lm = 0;
  188. for (int p = 0; p < trans.size(); p++) {
  189. for (int cnt = 0; cnt < tt.first[p]; cnt++) {
  190. int bits = (j >> lm) % (1 << trans[p]);
  191. for (int u = 0; u < optLen; u++) {
  192. s[j] += bin[optAnses[optLen][trans[p]][u][bits]][trans[p]];
  193. }
  194. lm += trans[p];
  195. }
  196. }
  197. }
  198. solve(n, w - vals[optLen][to]);
  199. return ;
  200. }
  201. for (int i = 0; i * 3 <= k; i++) {
  202. if (c1 != -1) break;
  203. for (int j = 0; i * 3 + j * 4 <= k; j++) {
  204. if (c1 != -1) break;
  205. for (int t = 0; i * 3 + j * 4 + t * 5 <= k; t++) {
  206. if (i * 3 + j * 4 + t * 5 == k) {
  207. c1 = i;
  208. c2 = j;
  209. c3 = t;
  210. break;
  211. }
  212. }
  213. }
  214. }
  215. assert(c1 != -1);
  216. if (w == 8 || w >= 11) {
  217. for (int kk = 0; kk < 5; kk++) {
  218. for (int j = 0; j < n; j++) {
  219. int lm = 0;
  220. for (int t = 0; t < c1; t++) {
  221. int b8 = (j >> (lm)) % 8;
  222. lm += 3;
  223. s[j] += bin[gg8[kk][b8]][3];
  224. }
  225. for (int t = 0; t < c2; t++) {
  226. int b16 = (j >> (lm)) % 16;
  227. lm += 4;
  228. s[j] += bin[gg16[kk][b16]][4];
  229. }
  230. for (int t = 0; t < c3; t++) {
  231. int b32 = (j >> (lm)) % 32;
  232. lm += 5;
  233. s[j] += bin[gg32[kk][b32]][5];
  234. }
  235. }
  236. }
  237. solve(n, w - 8);
  238. return ;
  239. }
  240. int f = w / 3;
  241. for (int i = 0; i < f; i++) {
  242. for (int j = 0; j < n; j++) {
  243. s[j] += bin[j][k];
  244. }
  245. for (int j = 0; j < n; j++) {
  246. int lm = 0;
  247. for (int t = 0; t < c1; t++) {
  248. int b8 = (j >> (lm)) % 8;
  249. lm += 3;
  250. s[j] += bin[f8[b8]][3];
  251. }
  252. for (int t = 0; t < c2; t++) {
  253. int b16 = (j >> (lm)) % 16;
  254. lm += 4;
  255. s[j] += bin[f16[b16]][4];
  256. }
  257. for (int t = 0; t < c3; t++) {
  258. int b32 = (j >> (lm)) % 32;
  259. lm += 5;
  260. s[j] += bin[f32[b32]][5];
  261. }
  262. }
  263. }
  264. for (int i = 0; i < w % 3; i++) {
  265. for (int j = 0; j < n; j++) {
  266. s[j] += bin[j][k];
  267. }
  268. }
  269. return ;
  270. }
  271. }
  272. int bits[maxN];
  273. mt19937 rnd(228);
  274. void go(int le, int x) {
  275. vector < vector < int > > best;
  276. int a = -1;
  277. int b = 0;
  278. for (int len = le; len <= le; len++) {
  279. for (int steps = 0; steps < (int)1e6; steps++) {
  280. vector < int > p(x);
  281. for (int i = 0; i < x; i++) {
  282. p[i] = i;
  283. }
  284. vector<vector<int> > all;
  285. vector<vector<int> > dist(x, vector<int>(x, 0));
  286. for (int j = 0; j < len; j++) {
  287. shuffle(p.begin(), p.end(), rnd);
  288. all.push_back(p);
  289. for (int k = 0; k < x; k++) {
  290. for (int t = 0; t < x; t++) {
  291. dist[k][t] += bits[p[k] ^ p[t]];
  292. }
  293. }
  294. }
  295. int mn = 100000;
  296. for (int k = 0; k < x; k++) {
  297. for (int t = k + 1; t < x; t++) {
  298. mn = min(mn, dist[k][t]);
  299. }
  300. }
  301. if (mn * b > a * len) {
  302. a = mn;
  303. b = len;
  304. best = all;
  305. }
  306. }
  307. }
  308. cout << a << " " << b << " " << (1.0 * a / b) << endl;
  309. cout << "{";
  310. for (int i = 0; i < best.size(); i++) {
  311. if (i != 0) cout << "," << endl;
  312. cout << "{";
  313. for (int j = 0; j < best[i].size(); j++) {
  314. if (j != 0) {
  315. cout << ", ";
  316. }
  317. cout << best[i][j];
  318. }
  319. cout << "}" << endl;
  320. }
  321. cout << "}" << endl;
  322. /*do {
  323. random_shuffle(p.begin(), p.end());
  324. bool ok = true;
  325. int cnt = 1000;
  326. for (int i = 0; i < x; i++) {
  327. for (int j = i + 1; j < x; j++) {
  328. int f = bits[p[i] ^ p[j]] + bits[i ^ j];
  329. if (f == 2) {
  330. ok = false;
  331. break;
  332. }
  333. cnt = min(cnt, f);
  334. }
  335. }
  336. if (ok && cnt >= 4) {
  337. for (int i = 0; i < x; i++) {
  338. if (i != 0) cout << ", ";
  339. cout << p[i];
  340. }
  341. break;
  342. }
  343. } while (true);*/
  344. return ;
  345. //exit(0);
  346. }
  347. int main() {
  348. ios_base::sync_with_stdio(false);
  349. cin.tie(nullptr);
  350. srand(228);
  351. //freopen("input.txt", "r", stdin);
  352. //freopen("output.txt", "w", stdout);
  353. for (int i = 1; i < maxN; i++) {
  354. bits[i] = bits[i / 2] + (i % 2);
  355. }
  356. optAnses[7][3] = {{6, 3, 1, 7, 2, 0, 5, 4}
  357. ,
  358. {2, 0, 4, 5, 7, 6, 3, 1}
  359. ,
  360. {0, 1, 5, 2, 7, 3, 4, 6}
  361. ,
  362. {5, 7, 2, 4, 3, 0, 6, 1}
  363. ,
  364. {5, 2, 3, 7, 4, 1, 0, 6}
  365. ,
  366. {6, 0, 5, 4, 7, 2, 3, 1}
  367. ,
  368. {5, 7, 0, 2, 4, 3, 6, 1}};
  369. vals[7][3] = 11;
  370. optAnses[7][4] = {{2, 0, 12, 3, 15, 13, 8, 5, 14, 4, 6, 10, 1, 9, 7, 11}
  371. ,
  372. {0, 4, 1, 11, 3, 2, 10, 8, 14, 9, 5, 12, 15, 13, 6, 7}
  373. ,
  374. {8, 3, 15, 11, 10, 4, 1, 12, 5, 9, 2, 14, 6, 13, 7, 0}
  375. ,
  376. {5, 15, 0, 4, 2, 9, 11, 13, 7, 10, 1, 14, 12, 6, 8, 3}
  377. ,
  378. {10, 7, 3, 0, 8, 11, 4, 13, 9, 2, 14, 15, 6, 5, 12, 1}
  379. ,
  380. {2, 7, 10, 3, 13, 9, 12, 14, 4, 1, 15, 8, 6, 5, 0, 11}
  381. ,
  382. {8, 14, 10, 13, 4, 2, 15, 1, 0, 3, 11, 5, 7, 6, 12, 9}
  383. };
  384. vals[7][4] = 12;
  385. optAnses[7][5] =
  386. {{31, 16, 20, 19, 14, 3, 23, 5, 26, 1, 7, 8, 25, 2, 11, 28, 21, 4, 13, 30, 12, 27, 15, 29, 17, 10, 6, 18, 9, 0, 22, 24}
  387. ,
  388. {5, 4, 17, 3, 29, 21, 31, 18, 25, 2, 15, 6, 7, 20, 0, 19, 28, 30, 16, 22, 13, 9, 12, 26, 1, 8, 14, 23, 11, 27, 10, 24}
  389. ,
  390. {26, 16, 0, 5, 7, 19, 10, 4, 22, 8, 9, 1, 12, 20, 17, 14, 3, 30, 27, 24, 15, 28, 31, 23, 13, 21, 25, 18, 6, 11, 29, 2}
  391. ,
  392. {0, 15, 13, 22, 21, 11, 17, 6, 7, 27, 26, 10, 16, 5, 29, 24, 18, 2, 14, 30, 23, 3, 4, 1, 8, 31, 9, 19, 28, 25, 12, 20}
  393. ,
  394. {12, 23, 25, 13, 11, 0, 19, 4, 27, 30, 5, 22, 16, 6, 15, 1, 24, 9, 2, 26, 20, 17, 10, 3, 28, 14, 29, 31, 8, 21, 18, 7}
  395. ,
  396. {9, 31, 16, 7, 2, 25, 27, 28, 30, 19, 26, 10, 17, 4, 13, 15, 24, 0, 18, 6, 23, 3, 21, 20, 29, 22, 12, 5, 14, 8, 1, 11}
  397. ,
  398. {17, 13, 23, 22, 27, 8, 16, 29, 9, 26, 11, 0, 21, 5, 14, 31, 6, 10, 25, 2, 7, 4, 20, 30, 12, 19, 18, 15, 1, 28, 3, 24}
  399. };
  400. vals[7][5] = 13;
  401. optAnses[7][6] =
  402. {{15, 19, 60, 36, 8, 54, 31, 50, 41, 51, 61, 33, 48, 1, 26, 43, 44, 21, 17, 27, 2, 13, 40, 20, 53, 46, 23, 5, 12, 4, 49, 3, 10, 47, 45, 24, 39, 62, 52, 63, 28, 14, 57, 58, 34, 6, 29, 7, 9, 25, 38, 22, 16, 56, 11, 32, 35, 30, 59, 37, 18, 0, 55, 42}
  403. ,
  404. {45, 41, 1, 16, 6, 25, 3, 59, 18, 14, 46, 20, 27, 47, 37, 56, 7, 2, 52, 23, 36, 34, 4, 28, 43, 32, 58, 39, 61, 30, 11, 24, 42, 10, 51, 12, 60, 55, 0, 22, 57, 21, 15, 26, 31, 8, 38, 49, 63, 54, 13, 50, 40, 17, 62, 48, 44, 33, 9, 35, 5, 29, 53, 19}
  405. ,
  406. {45, 9, 62, 6, 51, 43, 50, 30, 13, 19, 3, 47, 61, 32, 33, 57, 38, 53, 31, 7, 40, 10, 2, 52, 24, 42, 44, 14, 11, 15, 0, 39, 12, 48, 27, 17, 25, 54, 18, 1, 28, 29, 56, 60, 49, 34, 37, 59, 5, 58, 41, 4, 55, 20, 63, 16, 26, 46, 21, 36, 23, 8, 35, 22}
  407. ,
  408. {25, 60, 19, 22, 55, 2, 28, 53, 18, 54, 9, 1, 52, 30, 7, 58, 38, 40, 48, 0, 41, 10, 43, 63, 24, 35, 39, 15, 12, 32, 37, 42, 3, 17, 51, 14, 16, 61, 34, 33, 20, 47, 8, 44, 31, 62, 4, 36, 57, 6, 56, 11, 26, 29, 59, 45, 49, 21, 23, 5, 50, 46, 27, 13}
  409. ,
  410. {42, 50, 44, 41, 12, 58, 57, 20, 17, 35, 25, 56, 19, 54, 23, 4, 22, 45, 28, 63, 8, 30, 52, 43, 31, 37, 5, 29, 26, 32, 7, 16, 24, 47, 48, 6, 27, 11, 39, 49, 61, 14, 36, 10, 0, 51, 53, 46, 13, 15, 33, 2, 18, 1, 3, 21, 60, 9, 40, 59, 55, 38, 34, 62}
  411. ,
  412. {1, 44, 25, 52, 17, 62, 28, 54, 7, 14, 27, 4, 18, 26, 47, 46, 58, 22, 61, 29, 57, 23, 20, 21, 9, 45, 16, 30, 49, 8, 38, 0, 10, 41, 3, 5, 12, 11, 59, 35, 34, 13, 36, 40, 53, 24, 56, 51, 63, 15, 48, 6, 50, 43, 33, 31, 42, 39, 37, 55, 2, 19, 60, 32}
  413. ,
  414. {40, 38, 17, 25, 2, 10, 0, 42, 56, 37, 50, 52, 4, 62, 53, 26, 18, 32, 3, 28, 49, 51, 47, 41, 54, 43, 59, 60, 58, 61, 7, 15, 19, 9, 13, 14, 35, 36, 12, 20, 46, 57, 39, 16, 44, 45, 27, 48, 24, 1, 33, 21, 23, 8, 55, 22, 63, 11, 5, 6, 30, 34, 29, 31}
  415. };
  416. vals[7][6] = 14;
  417.  
  418. optAnses[6][3] = {{{1, 5, 4, 3, 0, 2, 7, 6}
  419. ,
  420. {0, 1, 5, 4, 7, 6, 3, 2}
  421. ,
  422. {7, 1, 6, 0, 3, 5, 4, 2}
  423. ,
  424. {5, 7, 2, 3, 0, 6, 1, 4}
  425. ,
  426. {1, 6, 5, 0, 2, 7, 3, 4}
  427. ,
  428. {5, 3, 2, 0, 1, 7, 6, 4}
  429. }};
  430. vals[6][3] = 10;
  431.  
  432. optAnses[6][4] = {{1, 2, 14, 7, 5, 3, 13, 15, 9, 8, 0, 11, 6, 4, 12, 10}
  433. ,
  434. {8, 10, 5, 3, 2, 11, 0, 12, 9, 13, 15, 4, 7, 1, 6, 14}
  435. ,
  436. {15, 13, 7, 11, 2, 4, 8, 9, 3, 12, 1, 14, 6, 0, 5, 10}
  437. ,
  438. {0, 15, 5, 3, 14, 6, 13, 4, 12, 1, 10, 7, 9, 2, 11, 8}
  439. ,
  440. {6, 2, 0, 11, 7, 13, 14, 4, 8, 5, 15, 1, 10, 9, 12, 3}
  441. ,
  442. {3, 10, 5, 1, 15, 7, 6, 9, 4, 0, 8, 11, 14, 2, 13, 12}
  443. };
  444.  
  445. vals[6][4] = 10;
  446.  
  447. optAnses[6][5] = {{18, 7, 13, 15, 4, 9, 26, 14, 12, 30, 25, 6, 31, 22, 23, 19, 16, 3, 8, 17, 2, 28, 21, 11, 20, 5, 0, 10, 27, 29, 24, 1}
  448. ,
  449. {20, 16, 14, 5, 28, 23, 9, 10, 13, 24, 17, 15, 30, 7, 8, 6, 1, 26, 29, 25, 3, 4, 19, 11, 12, 18, 0, 22, 27, 31, 2, 21}
  450. ,
  451. {3, 21, 30, 14, 28, 16, 9, 1, 2, 20, 18, 0, 31, 12, 17, 24, 23, 6, 11, 5, 10, 13, 8, 4, 25, 15, 27, 19, 29, 26, 22, 7}
  452. ,
  453. {10, 29, 1, 17, 16, 24, 11, 12, 14, 7, 21, 8, 31, 27, 26, 2, 4, 30, 0, 13, 18, 20, 3, 5, 6, 23, 9, 25, 28, 19, 15, 22}
  454. ,
  455. {12, 10, 9, 14, 17, 15, 0, 16, 8, 1, 5, 31, 7, 29, 2, 27, 6, 3, 11, 23, 24, 4, 28, 21, 30, 22, 26, 18, 13, 19, 25, 20}
  456. ,
  457. {31, 1, 26, 13, 5, 3, 30, 10, 22, 4, 20, 18, 19, 11, 27, 8, 2, 14, 16, 7, 25, 21, 0, 9, 15, 6, 23, 24, 29, 12, 28, 17}
  458. };
  459.  
  460. vals[6][5] = 11;
  461.  
  462. optAnses[6][6] = {{0, 33, 38, 40, 31, 62, 18, 61, 46, 32, 39, 27, 24, 17, 35, 12, 57, 59, 49, 54, 20, 19, 42, 9, 37, 8, 41, 47, 53, 58, 10, 1, 7, 28, 48, 29, 13, 50, 23, 43, 16, 36, 6, 2, 4, 21, 26, 3, 25, 56, 22, 55, 30, 11, 60, 5, 44, 63, 15, 51, 52, 45, 14, 34}
  463. ,
  464. {18, 46, 28, 42, 52, 23, 29, 31, 17, 32, 54, 4, 53, 59, 1, 3, 49, 16, 47, 45, 8, 34, 57, 27, 35, 33, 55, 63, 11, 39, 50, 13, 61, 22, 41, 7, 25, 5, 43, 0, 24, 20, 21, 15, 14, 56, 48, 12, 58, 26, 19, 51, 62, 2, 60, 44, 36, 38, 9, 30, 10, 40, 37, 6}
  465. ,
  466. {41, 20, 2, 6, 40, 30, 63, 8, 57, 43, 9, 3, 10, 28, 5, 21, 14, 15, 54, 33, 4, 49, 47, 36, 38, 59, 53, 58, 51, 11, 48, 60, 55, 62, 46, 27, 22, 13, 29, 7, 45, 42, 35, 16, 1, 34, 50, 32, 31, 26, 23, 17, 12, 25, 56, 37, 52, 18, 44, 0, 19, 39, 24, 61}
  467. ,
  468. {31, 21, 57, 26, 3, 42, 16, 58, 12, 63, 32, 2, 7, 30, 43, 20, 41, 19, 40, 56, 46, 27, 54, 59, 48, 29, 11, 9, 38, 60, 17, 6, 18, 55, 53, 23, 8, 0, 52, 36, 34, 4, 1, 25, 35, 37, 14, 39, 44, 33, 47, 51, 13, 62, 61, 45, 22, 50, 10, 24, 28, 5, 15, 49}
  469. ,
  470. {41, 55, 33, 61, 58, 60, 29, 31, 16, 54, 50, 10, 37, 36, 11, 42, 38, 63, 15, 1, 48, 52, 18, 19, 43, 40, 45, 57, 47, 28, 30, 22, 0, 13, 46, 34, 3, 53, 39, 35, 51, 6, 21, 14, 9, 27, 4, 12, 8, 56, 62, 7, 49, 5, 17, 20, 26, 2, 59, 25, 24, 23, 44, 32}
  471. ,
  472. {27, 37, 0, 48, 59, 16, 10, 43, 62, 14, 28, 33, 11, 44, 12, 5, 36, 55, 39, 31, 19, 17, 52, 2, 46, 35, 60, 51, 9, 29, 15, 3, 45, 54, 21, 41, 4, 34, 6, 38, 63, 23, 56, 30, 42, 26, 50, 47, 24, 53, 58, 18, 7, 61, 1, 13, 57, 25, 32, 8, 49, 40, 22, 20}
  473. };
  474.  
  475. vals[6][6] = 11;
  476.  
  477. lg[1] = 0;
  478. for (int i = 2; i < maxN; i++) {
  479. lg[i] = lg[(i + 1) / 2] + 1;
  480. }
  481. for (int i = 0; i < 12; i++) {
  482. for (int j = 0; j < (1 << i); j++) {
  483. for (int k = 0; k < i; k++) {
  484. bin[j][i] += ((j >> k) & 1) + '0';
  485. }
  486. }
  487. }
  488. int tst;
  489. cin >> tst;
  490. while (tst--) {
  491. cin >> n >> w >> m;
  492. w = 2 * w + 1;
  493. int nn = n;
  494. s.clear();
  495. s.resize(nn, "");
  496. solve(nn, w);
  497. printAns(s);
  498. }
  499. return 0;
  500. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!