# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
304264 | jtnydv25 | Counting Mushrooms (IOI20_mushrooms) | C++17 | 15 ms | 640 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 20;
const int T = 10;
vector<int> ask[1500];
int res[1500][M];
void pre(){
ask[1]={9,17,10,2,18,7,13,8,12,6,11,1,19,0,14,5,15,3,4,16};
res[1][0]=2;
res[1][1]=3;
res[1][2]=4;
ask[4]={10,4,0,13,5,11,14,7,2,12,6,1,8,9,3};
res[4][0]=5;
ask[5]={7,0,3,2,8,9,6,4,15,17,5,1};
res[5][0]=6;
ask[6]={5,0,7,4,8,18,1,2,3,9,6};
res[6][0]=7;
res[6][2]=8;
res[5][2]=9;
ask[9]={3,7,4,8,6,9,5,0,2,15,1};
res[9][0]=10;
res[9][2]=11;
res[4][1]=12;
ask[12]={3,4,9,2,17,7,0,5,8,1,6};
res[12][0]=13;
res[12][2]=14;
res[4][2]=15;
ask[15]={11,6,0,4,3,2,5,7,12,8,1,9};
res[15][0]=16;
ask[16]={13,5,2,9,8,1,0,6,7,3,4};
res[16][0]=17;
res[16][1]=18;
res[15][1]=19;
res[15][2]=20;
res[1][3]=21;
ask[21]={3,2,13,12,7,5,11,4,9,6,8,14,1,0,10};
res[21][0]=22;
ask[22]={17,16,1,18,7,0,9,5,3,8,6,2,4,15};
res[22][1]=23;
res[22][2]=24;
res[22][3]=25;
res[22][4]=26;
res[21][1]=27;
ask[27]={1,4,8,9,17,0,5,6,2,3,7};
res[27][0]=28;
res[27][2]=29;
res[21][2]=30;
ask[30]={13,0,5,3,6,7,12,2,8,9,1,4,16,11};
res[30][1]=31;
res[30][2]=32;
res[30][3]=33;
res[30][4]=34;
res[1][4]=35;
ask[35]={11,0,2,12,9,10,8,4,6,5,7,1,3,17};
res[35][0]=36;
ask[36]={9,1,6,0,14,7,4,3,8,5,2,13};
res[36][0]=37;
ask[37]={18,0,8,2,3,5,15,6,4,1,9,7};
res[37][1]=38;
res[37][2]=39;
res[37][3]=40;
res[36][1]=41;
ask[41]={15,6,2,7,8,18,5,0,3,1,4,9};
res[41][0]=42;
res[41][1]=43;
res[41][2]=44;
res[36][2]=45;
ask[45]={0,6,2,5,9,4,3,8,15,1,7,18};
res[45][0]=46;
res[45][1]=47;
res[45][2]=48;
res[36][3]=49;
res[35][1]=50;
ask[50]={11,2,0,13,1,7,6,5,8,3,9,14,4};
res[50][0]=51;
ask[51]={7,6,2,0,3,15,5,8,4,9,1,18};
res[51][0]=52;
res[51][1]=53;
res[51][2]=54;
res[50][1]=55;
ask[55]={9,6,7,1,4,8,0,5,15,2,3,18};
res[55][0]=56;
res[55][1]=57;
res[55][2]=58;
res[50][2]=59;
ask[59]={3,0,2,9,5,7,13,1,4,8,6};
res[59][0]=60;
res[59][2]=61;
res[50][3]=62;
ask[62]={13,9,2,3,7,5,4,8,0,1,6};
res[62][0]=63;
res[62][1]=64;
res[35][2]=65;
ask[65]={9,4,13,8,5,6,3,1,7,11,0,14,2,10};
res[65][0]=66;
ask[66]={3,9,1,6,8,7,2,0,5,4,18,15};
res[66][0]=67;
res[66][1]=68;
res[66][2]=69;
res[65][1]=70;
ask[70]={9,2,7,4,18,8,1,3,5,0,6,15};
res[70][0]=71;
res[70][1]=72;
res[70][2]=73;
res[65][2]=74;
ask[74]={0,5,3,6,9,11,7,2,4,1,8,13};
res[74][0]=75;
res[74][1]=76;
res[74][2]=77;
res[65][3]=78;
ask[78]={2,6,7,4,8,13,9,3,0,1,5};
res[78][0]=79;
res[78][2]=80;
res[35][3]=81;
ask[81]={14,3,10,7,1,9,6,13,5,8,15,4,2,0,11};
res[81][0]=82;
res[81][1]=83;
res[81][2]=84;
ask[84]={1,3,7,18,5,4,6,9,8,2,0};
res[84][0]=85;
res[84][2]=86;
res[81][3]=87;
ask[87]={1,4,5,6,2,8,11,3,9,7,0};
res[87][0]=88;
res[87][2]=89;
res[81][4]=90;
ask[90]={13,1,5,8,3,6,7,4,0,2,9};
res[90][0]=91;
res[90][1]=92;
res[35][4]=93;
ask[93]={11,2,3,1,4,7,8,6,9,5,0};
res[93][0]=94;
res[93][1]=95;
res[35][5]=96;
res[1][5]=97;
ask[97]={18,16,17,13,4,11,15,0,3,14,6,5,12,8,7,9,1,2,10};
res[97][1]=98;
ask[98]={3,1,9,7,6,17,4,8,2,0,5};
res[98][0]=99;
res[98][2]=100;
res[97][2]=101;
ask[101]={10,3,5,2,13,6,4,7,9,8,17,1,0};
res[101][1]=102;
res[101][2]=103;
res[101][3]=104;
res[101][4]=105;
res[97][3]=106;
ask[106]={10,4,8,6,7,12,0,13,1,9,2,5,3,16,11};
res[106][1]=107;
res[106][2]=108;
ask[108]={7,3,6,8,0,9,1,4,2,14,5};
res[108][0]=109;
res[108][2]=110;
res[106][3]=111;
ask[111]={2,9,6,4,8,1,0,5,7,3,17};
res[111][0]=112;
res[111][1]=113;
res[106][4]=114;
ask[114]={12,1,6,4,7,2,0,8,5,3,9};
res[114][0]=115;
res[114][1]=116;
res[106][5]=117;
res[97][4]=118;
ask[118]={11,16,4,14,5,9,3,8,7,1,0,6,17,2,12};
res[118][1]=119;
ask[119]={2,0,8,6,3,9,5,1,15,7,4};
res[119][0]=120;
res[119][2]=121;
res[118][2]=122;
ask[122]={9,6,1,13,7,8,5,4,2,0,3};
res[122][0]=123;
res[122][2]=124;
res[118][3]=125;
ask[125]={6,3,4,2,7,8,9,5,1,11,0};
res[125][0]=126;
res[125][2]=127;
res[118][4]=128;
ask[128]={7,5,3,6,0,14,9,1,4,2,8};
res[128][0]=129;
res[128][2]=130;
res[118][5]=131;
res[118][6]=132;
res[97][5]=133;
ask[133]={12,3,14,7,2,8,4,9,5,6,17,0,1,11};
res[133][0]=134;
ask[134]={9,3,13,1,2,8,6,4,0,7,5};
res[134][0]=135;
res[134][2]=136;
res[133][1]=137;
ask[137]={6,1,9,4,2,7,0,3,11,8,5};
res[137][0]=138;
res[137][2]=139;
res[133][2]=140;
ask[140]={5,0,9,1,8,3,2,6,7,4,14};
res[140][0]=141;
res[140][1]=142;
res[133][3]=143;
ask[143]={11,8,4,0,5,1,3,2,7,6,9};
res[143][0]=144;
res[143][1]=145;
res[133][4]=146;
res[97][6]=147;
ask[147]={11,5,14,0,10,8,7,9,6,4,1,2,3,16,12};
res[147][1]=148;
ask[148]={9,1,4,13,8,6,3,7,0,2,5};
res[148][0]=149;
res[148][2]=150;
res[147][2]=151;
ask[151]={7,4,1,2,11,3,8,9,5,6,0};
res[151][0]=152;
res[151][2]=153;
res[147][3]=154;
ask[154]={9,0,1,7,4,5,11,3,6,8,2};
res[154][0]=155;
res[154][2]=156;
res[147][4]=157;
ask[157]={1,2,3,13,5,4,8,9,0,7,6};
res[157][0]=158;
res[157][2]=159;
res[147][5]=160;
res[1][6]=161;
ask[161]={11,14,9,7,8,4,0,12,16,2,1,17,3,6,18,5,10,15,13};
res[161][1]=162;
ask[162]={8,4,11,7,1,5,9,3,0,2,6,10};
res[162][0]=163;
res[162][1]=164;
res[162][2]=165;
res[161][2]=166;
ask[166]={6,10,3,7,9,14,4,5,0,2,8,1,15};
res[166][0]=167;
res[166][1]=168;
res[166][2]=169;
res[166][3]=170;
res[161][3]=171;
ask[171]={17,3,4,8,11,6,1,5,14,2,15,9,7,0,10,12};
res[171][0]=172;
res[171][1]=173;
ask[173]={8,7,6,0,5,2,12,1,9,4,3};
res[173][0]=174;
res[173][2]=175;
res[171][2]=176;
ask[176]={3,13,5,1,4,8,6,9,7,2,0,14,10};
res[176][0]=177;
res[176][2]=178;
res[176][3]=179;
res[176][4]=180;
res[171][3]=181;
ask[181]={0,2,7,12,1,6,8,5,3,9,4,11};
res[181][0]=182;
res[181][1]=183;
res[181][2]=184;
res[181][3]=185;
res[171][4]=186;
ask[186]={14,6,7,9,11,5,3,4,10,0,8,2,1};
res[186][1]=187;
res[186][2]=188;
res[186][3]=189;
res[186][4]=190;
res[171][5]=191;
ask[191]={12,5,1,9,8,7,4,6,10,3,0,2};
res[191][0]=192;
res[191][1]=193;
res[191][2]=194;
res[171][6]=195;
ask[195]={4,8,6,7,5,0,2,3,1,14,9,10};
res[195][1]=196;
res[195][2]=197;
res[195][3]=198;
res[161][4]=199;
ask[199]={12,9,10,13,6,0,15,7,5,3,2,8,1,11,4,18};
res[199][0]=200;
res[199][1]=201;
ask[201]={14,9,8,5,3,12,7,4,0,2,6,1};
res[201][0]=202;
res[201][1]=203;
res[201][2]=204;
res[201][3]=205;
res[199][2]=206;
ask[206]={14,7,4,3,5,8,1,0,2,12,10,9,6};
res[206][0]=207;
res[206][1]=208;
res[206][2]=209;
res[206][3]=210;
res[199][3]=211;
ask[211]={12,4,0,2,3,1,8,6,9,10,5,7};
res[211][0]=212;
res[211][1]=213;
res[211][2]=214;
res[211][3]=215;
res[199][4]=216;
ask[216]={11,7,1,14,9,0,5,2,6,3,8,10,4};
res[216][1]=217;
res[216][2]=218;
res[216][3]=219;
res[216][4]=220;
res[199][5]=221;
ask[221]={12,3,10,4,0,2,9,6,7,5,1,8};
res[221][0]=222;
res[221][1]=223;
res[221][2]=224;
res[221][3]=225;
res[161][5]=226;
ask[226]={8,14,6,0,1,9,12,5,4,3,13,2,7,10};
res[226][0]=227;
ask[227]={17,9,0,6,4,5,3,15,7,2,1,8};
res[227][1]=228;
res[227][2]=229;
res[227][3]=230;
res[226][1]=231;
ask[231]={9,17,3,15,0,8,5,4,7,6,2,1};
res[231][0]=232;
res[231][2]=233;
res[231][4]=234;
res[226][2]=235;
ask[235]={17,7,6,0,1,15,3,9,8,5,2,11,4};
res[235][1]=236;
res[235][2]=237;
res[235][3]=238;
res[235][4]=239;
res[226][3]=240;
ask[240]={8,3,2,5,6,4,7,0,9,17,1,11};
res[240][0]=241;
res[240][1]=242;
res[240][2]=243;
res[240][3]=244;
res[226][4]=245;
ask[245]={3,0,2,5,1,17,6,8,7,4,9,12};
res[245][0]=246;
res[245][1]=247;
res[245][2]=248;
res[245][3]=249;
res[226][5]=250;
ask[250]={2,1,3,9,8,4,0,5,6,12,7};
res[250][0]=251;
res[250][2]=252;
res[226][6]=253;
res[161][6]=254;
ask[254]={11,5,9,0,10,2,3,8,1,17,4,6,7,13,18,12,14};
res[254][1]=255;
ask[255]={1,7,2,8,6,15,4,0,5,3,9};
res[255][0]=256;
res[255][2]=257;
res[254][2]=258;
res[254][3]=259;
ask[259]={17,0,6,3,7,5,4,12,9,2,8,1};
res[259][0]=260;
res[259][1]=261;
res[259][2]=262;
res[259][3]=263;
res[254][4]=264;
ask[264]={1,6,5,0,10,2,3,8,12,7,9,4,15};
res[264][1]=265;
res[264][2]=266;
res[264][3]=267;
res[264][4]=268;
res[254][5]=269;
ask[269]={10,7,8,5,6,3,17,0,1,2,9,15,4};
res[269][1]=270;
res[269][2]=271;
res[269][3]=272;
res[269][5]=273;
res[254][6]=274;
ask[274]={15,8,0,7,1,12,4,9,3,2,6,5};
res[274][0]=275;
res[274][1]=276;
res[274][2]=277;
res[274][3]=278;
res[254][7]=279;
res[161][7]=280;
ask[280]={11,4,9,2,5,3,8,1,0,7,12,6,10,14};
res[280][1]=281;
res[280][2]=282;
res[280][3]=283;
res[280][4]=284;
res[280][5]=285;
res[161][8]=286;
ask[286]={14,8,5,4,12,7,1,3,0,6,9,2};
res[286][1]=287;
res[286][2]=288;
res[286][3]=289;
res[1][7]=290;
ask[290]={13,4,12,5,9,1,6,11,0,3,7,8,17,2,10,14,16,18};
res[290][1]=291;
ask[291]={6,8,3,2,5,1,10,9,7,0,14,4,15};
res[291][1]=292;
res[291][2]=293;
res[291][3]=294;
res[291][4]=295;
res[290][2]=296;
ask[296]={15,9,5,2,6,7,4,10,0,3,1,14,8};
res[296][0]=297;
res[296][1]=298;
res[296][2]=299;
res[296][3]=300;
res[296][4]=301;
res[296][5]=302;
res[290][3]=303;
ask[303]={14,16,8,15,3,1,0,13,6,2,10,5,9,7,4,11};
res[303][1]=304;
ask[304]={3,0,7,4,6,5,2,1,9,12,8};
res[304][0]=305;
res[304][2]=306;
res[303][2]=307;
ask[307]={0,4,7,5,6,1,3,9,8,11,2,12};
res[307][0]=308;
res[307][1]=309;
res[307][2]=310;
res[303][3]=311;
ask[311]={4,1,8,2,9,0,7,5,6,11,3,10};
res[311][0]=312;
res[311][1]=313;
res[311][2]=314;
res[303][4]=315;
ask[315]={5,6,2,1,8,0,7,3,4,9,12,10};
res[315][0]=316;
res[315][1]=317;
res[315][2]=318;
res[303][5]=319;
ask[319]={10,8,7,0,3,5,11,1,2,9,4,6};
res[319][0]=320;
res[319][1]=321;
res[319][2]=322;
res[303][6]=323;
ask[323]={6,0,2,8,1,10,4,7,9,5,3};
res[323][0]=324;
res[323][2]=325;
res[290][4]=326;
ask[326]={10,4,12,0,13,9,11,3,1,18,2,14,8,6,7,5,16,15};
res[326][1]=327;
res[326][2]=328;
res[326][3]=329;
ask[329]={12,5,11,6,3,7,1,9,8,2,4,0};
res[329][0]=330;
res[329][1]=331;
res[329][2]=332;
res[326][4]=333;
ask[333]={9,1,8,7,2,5,4,3,0,6,10};
res[333][0]=334;
res[333][1]=335;
res[326][5]=336;
ask[336]={3,6,9,0,7,11,8,2,4,1,5,10};
res[336][0]=337;
res[336][1]=338;
res[336][2]=339;
res[326][6]=340;
ask[340]={8,3,12,5,1,6,7,4,0,9,2,11};
res[340][0]=341;
res[340][1]=342;
res[340][2]=343;
res[326][7]=344;
ask[344]={8,0,6,3,7,2,11,1,4,9,5,12};
res[344][0]=345;
res[344][1]=346;
res[344][2]=347;
res[326][8]=348;
ask[348]={5,9,0,11,7,3,8,2,6,1,4};
res[348][0]=349;
res[348][2]=350;
res[290][5]=351;
ask[351]={12,13,16,2,3,5,6,1,10,7,9,18,4,0,8,17};
res[351][1]=352;
ask[352]={1,9,6,0,2,8,3,7,5,4,15,14};
res[352][0]=353;
res[352][1]=354;
res[352][2]=355;
res[351][2]=356;
ask[356]={14,8,4,1,9,15,5,3,0,2,7,6};
res[356][0]=357;
res[356][1]=358;
res[356][2]=359;
res[351][3]=360;
ask[360]={15,3,6,8,1,0,4,9,14,5,7,2};
res[360][0]=361;
res[360][1]=362;
res[360][2]=363;
res[351][4]=364;
ask[364]={1,8,6,5,15,7,9,4,2,3,0};
res[364][0]=365;
res[364][2]=366;
res[351][5]=367;
ask[367]={12,5,7,6,2,4,8,10,3,0,1,9};
res[367][0]=368;
res[367][1]=369;
res[367][2]=370;
res[351][6]=371;
ask[371]={7,3,0,2,4,10,9,6,1,5,8};
res[371][0]=372;
res[371][2]=373;
res[351][7]=374;
ask[374]={0,3,2,15,7,8,5,9,6,1,4,12};
res[374][0]=375;
res[374][1]=376;
res[374][2]=377;
res[290][6]=378;
ask[378]={12,11,15,6,1,7,5,14,0,2,4,17,3,9,8};
res[378][1]=379;
ask[379]={15,6,1,2,7,8,4,10,0,5,3,9};
res[379][0]=380;
res[379][1]=381;
res[379][2]=382;
res[378][2]=383;
ask[383]={0,2,3,8,15,6,4,11,7,5,1,9};
res[383][0]=384;
res[383][2]=385;
res[383][4]=386;
res[378][3]=387;
ask[387]={2,0,4,6,9,5,3,1,7,11,8,10};
res[387][0]=388;
res[387][1]=389;
res[387][2]=390;
res[378][4]=391;
ask[391]={8,9,5,7,4,1,15,0,3,10,6,2};
res[391][0]=392;
res[391][2]=393;
res[391][4]=394;
res[378][5]=395;
ask[395]={4,0,14,1,7,6,3,5,2,9,10,8};
res[395][0]=396;
res[395][2]=397;
res[395][4]=398;
res[378][6]=399;
ask[399]={1,10,6,8,3,9,2,7,4,0,5};
res[399][0]=400;
res[399][2]=401;
res[290][7]=402;
ask[402]={11,13,2,6,5,3,0,10,8,1,9,4,7,15};
res[402][1]=403;
ask[403]={7,3,1,6,5,12,2,4,0,9,8};
res[403][0]=404;
res[403][2]=405;
res[402][2]=406;
ask[406]={4,1,2,0,3,9,5,8,7,6,10};
res[406][0]=407;
res[406][1]=408;
res[402][3]=409;
ask[409]={3,2,7,6,4,9,13,1,8,5,0};
res[409][0]=410;
res[409][2]=411;
res[402][4]=412;
ask[412]={2,7,9,12,8,5,6,3,4,1,0};
res[412][0]=413;
res[412][2]=414;
res[402][5]=415;
res[290][8]=416;
ask[416]={10,6,8,5,3,1,4,13,0,14,15,9,2,7,16,12,11};
res[416][1]=417;
res[416][2]=418;
res[416][3]=419;
res[416][4]=420;
res[416][5]=421;
res[416][6]=422;
res[290][9]=423;
ask[423]={6,7,11,4,9,3,8,2,0,5,1};
res[423][0]=424;
res[423][2]=425;
res[290][10]=426;
res[1][8]=427;
ask[427]={12,7,4,17,5,9,1,11,0,6,3,10,8,2};
res[427][0]=428;
ask[428]={15,14,13,8,2,9,7,6,4,0,5,3,18,1,19};
res[428][2]=429;
res[428][3]=430;
res[428][4]=431;
res[428][5]=432;
res[428][6]=433;
res[427][1]=434;
ask[434]={15,18,12,8,2,5,3,9,6,7,1,13,4,14,0};
res[434][1]=435;
res[434][3]=436;
ask[436]={0,4,5,1,8,2,6,9,7,13,3};
res[436][0]=437;
res[436][2]=438;
res[434][4]=439;
ask[439]={2,3,9,4,7,8,5,6,13,1,0};
res[439][0]=440;
res[439][2]=441;
res[434][5]=442;
ask[442]={8,4,2,5,6,1,0,3,7,9,13};
res[442][0]=443;
res[442][1]=444;
res[434][6]=445;
ask[445]={2,18,6,9,8,0,3,7,4,5,1};
res[445][0]=446;
res[445][2]=447;
res[434][7]=448;
res[427][2]=449;
ask[449]={14,10,13,8,6,11,4,1,3,7,9,17,2,5,0};
res[449][1]=450;
ask[450]={3,18,6,1,4,14,15,10,9,5,8,0,7,2,13};
res[450][2]=451;
res[450][3]=452;
res[450][4]=453;
res[450][5]=454;
res[450][6]=455;
res[450][7]=456;
res[449][2]=457;
ask[457]={18,19,15,5,4,6,0,2,1,13,11,12,8,9,3,7,10};
res[457][1]=458;
res[457][2]=459;
res[457][3]=460;
res[457][4]=461;
res[457][5]=462;
res[457][6]=463;
res[449][3]=464;
ask[464]={0,7,8,5,15,6,1,2,11,3,9,4,14,17,18};
res[464][1]=465;
res[464][3]=466;
res[464][4]=467;
res[464][5]=468;
res[464][6]=469;
res[464][7]=470;
res[449][4]=471;
ask[471]={18,0,15,2,1,8,5,6,11,3,9,7,4,13,17};
res[471][2]=472;
res[471][3]=473;
res[471][4]=474;
res[471][5]=475;
res[471][6]=476;
res[471][7]=477;
res[449][5]=478;
ask[478]={5,7,3,4,1,8,2,0,15,9,6,14,18,13,11};
res[478][1]=479;
res[478][2]=480;
res[478][3]=481;
res[478][4]=482;
res[478][5]=483;
res[478][6]=484;
res[427][3]=485;
ask[485]={3,4,1,17,8,12,11,13,6,9,5,2,10,0,7,14};
res[485][2]=486;
ask[486]={7,4,3,12,15,11,2,9,13,0,8,1,5,6,18};
res[486][2]=487;
res[486][3]=488;
res[486][4]=489;
res[486][5]=490;
res[486][6]=491;
res[486][7]=492;
res[485][3]=493;
ask[493]={18,11,1,4,3,9,7,13,0,2,6,5,8,15};
res[493][1]=494;
res[493][2]=495;
res[493][3]=496;
res[493][4]=497;
res[485][4]=498;
ask[498]={15,1,18,8,10,6,2,3,5,9,7,4,0,12,17};
res[498][2]=499;
res[498][3]=500;
res[498][4]=501;
res[498][5]=502;
res[498][6]=503;
res[498][7]=504;
res[485][5]=505;
ask[505]={10,5,7,6,18,1,4,9,0,8,2,12,15,14,3};
res[505][2]=506;
res[505][3]=507;
res[505][4]=508;
res[505][5]=509;
res[505][6]=510;
res[505][7]=511;
res[485][6]=512;
ask[512]={5,2,6,3,8,13,15,12,1,18,9,0,7,4,10};
res[512][2]=513;
res[512][3]=514;
res[512][4]=515;
res[512][5]=516;
res[512][6]=517;
res[512][7]=518;
res[485][7]=519;
ask[519]={7,5,6,8,3,4,1,0,9,10,2};
res[519][0]=520;
res[519][2]=521;
res[427][4]=522;
ask[522]={15,6,13,7,14,3,1,17,11,18,4,8,2,10,5,0,9};
res[522][2]=523;
res[522][3]=524;
ask[524]={5,7,6,0,8,9,3,18,2,1,4};
res[524][0]=525;
res[524][2]=526;
res[522][4]=527;
ask[527]={7,2,10,0,6,1,4,9,8,3,18,5,13};
res[527][0]=528;
res[527][1]=529;
res[527][2]=530;
res[527][3]=531;
res[527][4]=532;
res[522][5]=533;
ask[533]={10,0,1,5,18,6,3,13,9,7,4,8,2};
res[533][0]=534;
res[533][1]=535;
res[533][2]=536;
res[533][3]=537;
res[522][6]=538;
ask[538]={13,3,8,6,9,2,1,10,5,18,0,4,7};
res[538][1]=539;
res[538][2]=540;
res[538][3]=541;
res[538][4]=542;
res[538][5]=543;
res[522][7]=544;
ask[544]={14,5,4,6,13,9,1,0,7,11,3,2,8};
res[544][0]=545;
res[544][1]=546;
res[544][2]=547;
res[544][3]=548;
res[544][4]=549;
res[522][8]=550;
ask[550]={14,4,13,0,5,9,8,6,11,3,1,2,7};
res[550][1]=551;
res[550][2]=552;
res[550][3]=553;
res[550][5]=554;
res[522][9]=555;
ask[555]={7,3,5,13,0,1,2,8,4,9,6,14};
res[555][1]=556;
res[555][2]=557;
res[555][3]=558;
res[522][10]=559;
res[427][5]=560;
ask[560]={10,5,3,17,4,0,12,11,15,9,6,8,14,7,13,2,1,18};
res[560][3]=561;
ask[561]={9,5,3,6,4,0,7,2,15,1,8};
res[561][0]=562;
res[561][2]=563;
res[560][4]=564;
ask[564]={1,8,6,10,2,4,0,9,3,7,5,15};
res[564][0]=565;
res[564][1]=566;
res[564][2]=567;
res[560][5]=568;
ask[568]={13,0,2,9,6,5,1,3,10,8,4,7};
res[568][0]=569;
res[568][2]=570;
res[568][3]=571;
res[560][6]=572;
ask[572]={10,8,9,7,3,6,13,5,2,1,4,0};
res[572][0]=573;
res[572][1]=574;
res[572][2]=575;
res[560][7]=576;
ask[576]={14,8,0,13,2,1,3,4,9,5,7,6};
res[576][0]=577;
res[576][1]=578;
res[576][2]=579;
res[560][8]=580;
ask[580]={13,2,3,0,8,4,6,9,7,14,5,1};
res[580][0]=581;
res[580][1]=582;
res[580][2]=583;
res[560][9]=584;
ask[584]={14,9,0,4,6,1,13,8,2,3,7,5};
res[584][1]=585;
res[584][2]=586;
res[584][3]=587;
res[427][6]=588;
ask[588]={14,7,0,4,15,5,6,3,8,10,13,11,9,1,2};
res[588][2]=589;
ask[589]={7,1,6,3,8,2,0,18,5,4,9};
res[589][0]=590;
res[589][2]=591;
res[588][3]=592;
res[588][4]=593;
ask[593]={8,9,2,5,1,6,3,13,0,7,4};
res[593][0]=594;
res[593][2]=595;
res[588][5]=596;
ask[596]={6,1,9,3,18,5,4,7,0,2,8};
res[596][0]=597;
res[596][2]=598;
res[588][6]=599;
ask[599]={1,7,6,5,3,2,18,0,9,4,8};
res[599][0]=600;
res[599][2]=601;
res[588][7]=602;
res[427][7]=603;
ask[603]={13,9,10,14,17,4,7,6,18,0,2,3,8,1,5,12,15};
res[603][4]=604;
res[603][5]=605;
res[603][6]=606;
res[603][7]=607;
res[603][8]=608;
res[1][9]=609;
ask[609]={1,0,6,3,17,4,10,2,11,19,14,16,15,13,9,8,5,18,7,12};
res[609][2]=610;
ask[610]={9,3,4,8,7,6,2,0,1,5,11};
res[610][0]=611;
res[610][1]=612;
res[609][3]=613;
ask[613]={6,8,3,1,13,2,4,9,0,7,5,11};
res[613][0]=614;
res[613][1]=615;
res[613][2]=616;
res[609][4]=617;
ask[617]={11,16,5,6,12,1,13,9,8,0,15,2,14,7,3,4,10};
res[617][3]=618;
ask[618]={4,5,9,0,6,7,1,3,2,8,17};
res[618][0]=619;
res[618][1]=620;
res[617][4]=621;
res[617][5]=622;
ask[622]={3,2,8,5,9,14,6,4,1,0,7};
res[622][0]=623;
res[622][2]=624;
res[617][6]=625;
ask[625]={1,17,9,8,4,5,0,6,3,2,7};
res[625][0]=626;
res[625][2]=627;
res[617][7]=628;
ask[628]={3,6,5,10,7,2,0,9,8,1,4};
res[628][0]=629;
res[628][2]=630;
res[617][8]=631;
ask[631]={9,6,0,2,5,8,17,3,7,4,1};
res[631][0]=632;
res[631][2]=633;
res[617][9]=634;
res[609][5]=635;
ask[635]={19,9,13,0,8,2,6,10,5,11,4,3,7,16,14,12,1};
res[635][2]=636;
ask[636]={6,1,9,3,2,5,17,7,4,8,0};
res[636][0]=637;
res[636][2]=638;
res[635][3]=639;
ask[639]={3,8,4,6,17,5,9,2,0,7,1};
res[639][0]=640;
res[639][2]=641;
res[635][4]=642;
ask[642]={9,7,10,0,2,5,6,3,1,8,4};
res[642][0]=643;
res[642][2]=644;
res[635][5]=645;
ask[645]={7,4,2,3,1,0,10,9,6,8,5};
res[645][0]=646;
res[645][2]=647;
res[635][6]=648;
ask[648]={8,7,4,2,5,1,9,3,6,17,0};
res[648][0]=649;
res[648][2]=650;
res[635][7]=651;
ask[651]={9,8,4,0,5,11,3,2,7,1,6};
res[651][0]=652;
res[651][2]=653;
res[635][8]=654;
ask[654]={10,5,6,0,3,1,4,7,9,8,2};
res[654][0]=655;
res[654][1]=656;
res[609][6]=657;
ask[657]={7,11,3,10,1,12,4,6,9,16,17,15,2,5,8,0,13};
res[657][2]=658;
ask[658]={7,0,4,9,2,5,3,15,8,6,1};
res[658][0]=659;
res[658][2]=660;
res[657][3]=661;
ask[661]={18,0,2,1,6,3,14,5,9,4,7,8};
res[661][0]=662;
res[661][1]=663;
res[661][2]=664;
res[661][3]=665;
res[657][4]=666;
ask[666]={15,7,2,3,0,4,6,8,5,9,10,1,14};
res[666][1]=667;
res[666][2]=668;
res[666][3]=669;
res[666][4]=670;
res[657][5]=671;
ask[671]={10,5,4,15,3,0,2,7,11,6,9,8,1};
res[671][1]=672;
res[671][2]=673;
res[671][3]=674;
res[671][4]=675;
res[657][6]=676;
ask[676]={10,8,7,2,4,6,3,0,9,14,5,11,1};
res[676][2]=677;
res[676][3]=678;
res[676][4]=679;
res[676][5]=680;
res[657][7]=681;
ask[681]={18,6,9,4,5,3,0,8,1,7,10,2};
res[681][1]=682;
res[681][2]=683;
res[681][3]=684;
res[657][8]=685;
ask[685]={3,8,7,5,4,14,1,6,2,9,0};
res[685][0]=686;
res[685][2]=687;
res[657][9]=688;
res[609][7]=689;
ask[689]={13,3,2,8,14,6,0,10,9,4,1,5,7,16,11};
res[689][1]=690;
ask[690]={15,8,17,2,4,1,5,6,9,7,0,3};
res[690][0]=691;
res[690][1]=692;
res[690][2]=693;
res[690][3]=694;
res[689][2]=695;
ask[695]={2,8,5,9,6,1,0,17,4,3,7,18};
res[695][0]=696;
res[695][1]=697;
res[695][2]=698;
res[695][3]=699;
res[689][3]=700;
ask[700]={3,4,9,8,10,5,1,7,15,0,6,2,17};
res[700][0]=701;
res[700][1]=702;
res[700][2]=703;
res[700][4]=704;
res[689][4]=705;
ask[705]={10,9,2,7,4,0,6,1,5,18,8,3};
res[705][0]=706;
res[705][1]=707;
res[705][2]=708;
res[705][3]=709;
res[689][5]=710;
ask[710]={7,17,4,9,5,6,3,0,2,1,8,10};
res[710][0]=711;
res[710][1]=712;
res[710][2]=713;
res[710][3]=714;
res[689][6]=715;
ask[715]={1,2,0,8,5,6,7,17,9,3,4,15};
res[715][0]=716;
res[715][2]=717;
res[715][3]=718;
res[689][7]=719;
res[609][8]=720;
ask[720]={8,13,11,16,3,4,6,5,1,0,15,9,10,2,7,14};
res[720][2]=721;
ask[721]={9,6,8,5,2,13,3,0,4,7,1,17};
res[721][1]=722;
res[721][2]=723;
res[721][3]=724;
res[720][3]=725;
ask[725]={0,9,6,2,7,8,4,5,1,13,3,17};
res[725][1]=726;
res[725][2]=727;
res[725][3]=728;
res[720][4]=729;
ask[729]={11,9,6,13,1,0,4,5,8,7,2,10,3};
res[729][0]=730;
res[729][1]=731;
res[729][3]=732;
res[729][5]=733;
res[720][5]=734;
ask[734]={11,6,9,13,0,8,7,4,2,1,5,3};
res[734][0]=735;
res[734][1]=736;
res[734][2]=737;
res[734][3]=738;
res[720][6]=739;
ask[739]={5,4,6,11,7,13,9,2,8,17,0,1,3};
res[739][0]=740;
res[739][2]=741;
res[739][4]=742;
res[739][6]=743;
res[720][7]=744;
ask[744]={13,7,6,5,11,2,4,3,8,17,0,9,1};
res[744][1]=745;
res[744][2]=746;
res[744][3]=747;
res[744][4]=748;
res[720][8]=749;
ask[749]={6,3,0,1,8,18,9,4,7,5,2};
res[749][0]=750;
res[749][2]=751;
res[609][9]=752;
ask[752]={0,6,9,16,13,12,2,10,1,7,4,8,3,5,14,15,11};
res[752][2]=753;
ask[753]={17,0,4,3,9,18,1,7,6,8,2,5};
res[753][1]=754;
res[753][2]=755;
res[753][3]=756;
res[752][3]=757;
ask[757]={17,4,0,3,5,2,8,6,1,9,7};
res[757][0]=758;
res[757][1]=759;
res[752][4]=760;
ask[760]={0,5,6,4,10,3,8,7,2,9,1,18};
res[760][1]=761;
res[760][2]=762;
res[760][3]=763;
res[752][5]=764;
ask[764]={7,10,2,0,8,1,9,6,3,5,4};
res[764][0]=765;
res[764][2]=766;
res[752][6]=767;
ask[767]={6,4,8,3,1,0,2,13,9,5,7};
res[767][0]=768;
res[767][2]=769;
res[752][7]=770;
ask[770]={0,7,1,9,2,3,6,4,15,8,5,17};
res[770][0]=771;
res[770][1]=772;
res[770][3]=773;
res[752][8]=774;
ask[774]={4,0,9,7,3,6,2,8,18,5,1,14};
res[774][0]=775;
res[774][2]=776;
res[774][3]=777;
res[752][9]=778;
res[609][10]=779;
ask[779]={0,2,10,6,17,3,5,8,1,11,4,14,7,9,13};
res[779][3]=780;
ask[780]={4,2,3,8,1,5,0,10,7,6,9};
res[780][0]=781;
res[780][2]=782;
res[779][4]=783;
res[779][5]=784;
ask[784]={0,2,7,3,5,8,9,6,1,4,10};
res[784][0]=785;
res[784][1]=786;
res[779][6]=787;
ask[787]={2,7,5,8,15,0,9,1,3,4,6};
res[787][0]=788;
res[787][2]=789;
res[779][7]=790;
ask[790]={4,6,2,7,11,8,3,5,1,0,9};
res[790][0]=791;
res[790][2]=792;
res[779][8]=793;
res[779][9]=794;
res[609][11]=795;
ask[795]={18,13,10,7,4,0,2,9,1,3,6,5,11,8};
res[795][1]=796;
res[795][2]=797;
res[795][3]=798;
res[795][4]=799;
res[795][5]=800;
res[609][12]=801;
ask[801]={9,3,1,6,0,7,11,8,5,2,4};
res[801][0]=802;
res[801][2]=803;
res[1][10]=804;
ask[804]={10,3,4,1,5,18,7,2,14,6,16,8,0,11,9,17,15,13,19,12};
res[804][1]=805;
res[804][2]=806;
ask[806]={3,6,0,7,1,4,8,17,2,5,9};
res[806][0]=807;
res[806][2]=808;
res[804][3]=809;
ask[809]={11,4,7,3,6,8,0,5,14,9,1,2};
res[809][0]=810;
res[809][1]=811;
res[809][2]=812;
res[804][4]=813;
ask[813]={11,3,9,7,14,5,4,6,10,2,1,12,8,0};
res[813][0]=814;
res[813][1]=815;
res[813][2]=816;
res[813][4]=817;
res[813][5]=818;
res[813][6]=819;
res[804][5]=820;
ask[820]={14,4,0,5,9,8,6,11,7,2,12,1,3,13,10};
res[820][1]=821;
ask[821]={9,8,3,5,2,17,4,6,0,1,7};
res[821][0]=822;
res[821][2]=823;
res[820][2]=824;
ask[824]={10,6,4,0,2,17,9,3,1,7,8,5};
res[824][1]=825;
res[824][2]=826;
res[824][3]=827;
res[820][3]=828;
ask[828]={0,1,2,5,3,7,4,10,8,9,6,17};
res[828][1]=829;
res[828][2]=830;
res[828][3]=831;
res[820][4]=832;
ask[832]={6,7,5,2,9,3,1,0,4,11,8,15};
res[832][0]=833;
res[832][1]=834;
res[832][3]=835;
res[820][5]=836;
ask[836]={1,15,2,0,9,6,3,5,7,17,8,4};
res[836][0]=837;
res[836][2]=838;
res[836][4]=839;
res[820][6]=840;
ask[840]={7,5,6,17,1,0,15,8,3,2,9,4};
res[840][0]=841;
res[840][2]=842;
res[840][4]=843;
res[820][7]=844;
res[804][6]=845;
ask[845]={11,13,7,8,9,17,0,2,4,6,10,1,12,5,3};
res[845][1]=846;
ask[846]={1,2,5,4,3,14,7,0,6,8,9};
res[846][0]=847;
res[846][2]=848;
res[845][2]=849;
res[845][3]=850;
ask[850]={6,7,0,5,2,4,14,8,1,9,3};
res[850][0]=851;
res[850][2]=852;
res[845][4]=853;
ask[853]={14,7,9,12,0,5,4,8,6,1,15,2,10,3};
res[853][3]=854;
res[853][5]=855;
res[853][6]=856;
res[853][7]=857;
res[845][5]=858;
ask[858]={15,8,3,14,5,13,2,1,4,0,6,9,7};
res[858][0]=859;
res[858][1]=860;
res[858][2]=861;
res[858][3]=862;
res[845][6]=863;
ask[863]={9,7,2,13,8,5,6,0,1,4,3,14};
res[863][0]=864;
res[863][1]=865;
res[863][2]=866;
res[863][3]=867;
res[845][7]=868;
ask[868]={13,3,8,4,7,5,0,2,6,1,15,9};
res[868][1]=869;
res[868][2]=870;
res[868][3]=871;
res[845][8]=872;
ask[872]={14,5,15,6,2,7,0,8,9,3,1,4};
res[872][0]=873;
res[872][1]=874;
res[872][2]=875;
res[872][3]=876;
res[804][7]=877;
ask[877]={11,7,5,0,1,10,6,2,3,13,4,15,8,9,14,19};
res[877][1]=878;
res[877][2]=879;
ask[879]={17,6,1,4,9,0,14,3,5,2,8,7};
res[879][1]=880;
res[879][2]=881;
res[879][3]=882;
res[877][3]=883;
ask[883]={4,11,7,9,0,2,3,6,5,8,1};
res[883][0]=884;
res[883][2]=885;
res[877][4]=886;
ask[886]={1,8,5,7,2,9,14,4,3,6,0,11};
res[886][1]=887;
res[886][2]=888;
res[886][3]=889;
res[877][5]=890;
ask[890]={3,9,2,13,4,8,5,0,10,7,1,6};
res[890][0]=891;
res[890][2]=892;
res[890][4]=893;
res[877][6]=894;
ask[894]={10,8,7,6,9,14,3,4,0,1,2,5};
res[894][1]=895;
res[894][2]=896;
res[894][3]=897;
res[877][7]=898;
ask[898]={10,5,7,4,3,2,1,6,8,9,17,0};
res[898][0]=899;
res[898][1]=900;
res[898][3]=901;
res[877][8]=902;
ask[902]={9,4,7,1,8,6,0,5,17,2,3};
res[902][0]=903;
res[902][2]=904;
res[877][9]=905;
ask[905]={17,9,5,1,8,7,0,6,4,3,2};
res[905][0]=906;
res[905][1]=907;
res[804][8]=908;
ask[908]={13,6,0,12,7,9,4,8,5,15,1,2,10,3,11};
res[908][1]=909;
res[908][2]=910;
ask[910]={17,4,13,2,6,5,11,0,14,3,7,9,1,8};
res[910][3]=911;
res[910][5]=912;
res[910][6]=913;
res[910][7]=914;
res[908][3]=915;
ask[915]={18,4,14,7,6,5,3,8,9,1,0,2};
res[915][1]=916;
res[915][2]=917;
res[915][3]=918;
res[908][4]=919;
ask[919]={1,8,9,2,5,10,0,6,7,4,3};
res[919][0]=920;
res[919][2]=921;
res[908][5]=922;
ask[922]={7,9,2,1,8,3,5,4,11,0,17,6,14};
res[922][1]=923;
res[922][3]=924;
res[922][4]=925;
res[922][5]=926;
res[908][6]=927;
ask[927]={3,8,1,14,4,17,7,9,5,6,0,2,11};
res[927][1]=928;
res[927][2]=929;
res[927][3]=930;
res[927][4]=931;
res[908][7]=932;
ask[932]={17,8,3,14,6,2,1,0,4,5,9,7};
res[932][0]=933;
res[932][1]=934;
res[932][2]=935;
res[932][3]=936;
res[804][9]=937;
ask[937]={14,2,7,9,4,1,11,5,13,0,18,3,6,12,8,17};
res[937][3]=938;
ask[938]={7,9,8,5,1,11,3,4,6,0,2};
res[938][0]=939;
res[938][2]=940;
res[937][4]=941;
ask[941]={4,14,9,3,6,7,0,2,8,1,5,11};
res[941][1]=942;
res[941][2]=943;
res[941][3]=944;
res[937][5]=945;
ask[945]={14,9,6,1,5,4,8,15,3,7,0,2};
res[945][1]=946;
res[945][2]=947;
res[945][3]=948;
res[937][6]=949;
ask[949]={11,6,4,0,7,9,13,8,3,5,2,1};
res[949][1]=950;
res[949][2]=951;
res[949][3]=952;
res[937][7]=953;
ask[953]={10,8,6,0,2,9,4,7,14,1,3,5};
res[953][1]=954;
res[953][2]=955;
res[953][3]=956;
res[937][8]=957;
ask[957]={13,6,7,11,0,2,1,8,4,9,3,5};
res[957][1]=958;
res[957][2]=959;
res[957][3]=960;
res[937][9]=961;
ask[961]={14,6,3,7,0,9,8,4,5,1,2};
res[961][0]=962;
res[961][1]=963;
res[804][10]=964;
ask[964]={13,1,9,6,17,4,0,5,3,8,12,7,2,10,14,11};
res[964][1]=965;
res[964][3]=966;
res[964][4]=967;
res[964][5]=968;
res[964][6]=969;
res[964][7]=970;
res[964][8]=971;
res[804][11]=972;
ask[972]={8,3,0,6,7,13,9,2,4,1,5};
res[972][0]=973;
res[972][2]=974;
res[1][11]=975;
ask[975]={1,5,7,15,2,17,4,12,8,9,3,0,6,14,11,13,16,18,10};
res[975][1]=976;
ask[976]={1,7,5,0,2,4,8,14,3,6,9};
res[976][0]=977;
res[976][2]=978;
res[975][2]=979;
res[975][3]=980;
ask[980]={14,9,0,6,5,4,2,8,13,15,10,7,11,1,3};
res[980][2]=981;
res[980][4]=982;
ask[982]={3,11,6,5,8,9,2,7,4,0,1};
res[982][0]=983;
res[982][2]=984;
res[980][5]=985;
ask[985]={3,9,7,5,6,11,1,4,8,2,0};
res[985][0]=986;
res[985][2]=987;
res[980][6]=988;
ask[988]={5,6,3,0,9,1,8,2,12,4,7};
res[988][0]=989;
res[988][2]=990;
res[980][7]=991;
ask[991]={17,5,4,2,1,3,6,8,0,7,9};
res[991][0]=992;
res[991][1]=993;
res[975][4]=994;
ask[994]={5,6,9,4,2,12,3,7,0,1,8,11,15,14};
res[994][1]=995;
ask[995]={4,3,0,18,5,7,2,8,9,6,1};
res[995][0]=996;
res[995][2]=997;
res[994][2]=998;
ask[998]={3,6,4,8,0,9,15,5,1,7,2};
res[998][0]=999;
res[998][2]=1000;
res[994][3]=1001;
ask[1001]={18,0,1,3,6,5,9,8,4,2,7};
res[1001][0]=1002;
res[1001][1]=1003;
res[994][4]=1004;
res[994][5]=1005;
ask[1005]={9,8,6,7,4,0,3,1,18,5,2};
res[1005][0]=1006;
res[1005][2]=1007;
res[975][5]=1008;
ask[1008]={16,15,10,6,1,9,17,3,8,13,4,5,7,11,2,0,14};
res[1008][1]=1009;
res[1008][2]=1010;
res[1008][3]=1011;
ask[1011]={7,8,3,5,11,1,9,2,4,6,0};
res[1011][0]=1012;
res[1011][2]=1013;
res[1008][4]=1014;
ask[1014]={9,0,3,6,4,8,12,2,7,5,1,11};
res[1014][0]=1015;
res[1014][1]=1016;
res[1014][2]=1017;
res[1008][5]=1018;
ask[1018]={2,1,7,12,9,8,0,6,11,3,5,4};
res[1018][0]=1019;
res[1018][2]=1020;
res[1018][4]=1021;
res[1008][6]=1022;
ask[1022]={12,5,2,7,0,1,11,6,3,4,9,8};
res[1022][1]=1023;
res[1022][2]=1024;
res[1022][3]=1025;
res[1008][7]=1026;
ask[1026]={12,6,0,1,7,8,2,5,3,9,11,4};
res[1026][1]=1027;
res[1026][2]=1028;
res[1026][3]=1029;
res[1008][8]=1030;
ask[1030]={1,6,2,12,4,3,7,0,8,11,9,5};
res[1030][0]=1031;
res[1030][2]=1032;
res[1030][4]=1033;
res[1008][9]=1034;
res[1008][10]=1035;
res[975][6]=1036;
ask[1036]={14,7,8,5,0,11,9,6,2,3,4,16,18,13,1};
res[1036][2]=1037;
ask[1037]={12,9,0,8,15,7,4,5,2,1,3,6};
res[1037][1]=1038;
res[1037][2]=1039;
res[1037][3]=1040;
res[1036][3]=1041;
ask[1041]={4,7,5,6,0,9,2,3,8,1,15,12};
res[1041][0]=1042;
res[1041][1]=1043;
res[1041][2]=1044;
res[1036][4]=1045;
ask[1045]={2,8,4,5,9,7,12,0,6,1,3,15};
res[1045][1]=1046;
res[1045][2]=1047;
res[1045][3]=1048;
res[1036][5]=1049;
ask[1049]={15,12,2,4,7,0,3,6,8,9,5,1};
res[1049][0]=1050;
res[1049][1]=1051;
res[1049][2]=1052;
res[1036][6]=1053;
ask[1053]={4,9,5,2,3,0,7,6,12,1,8,15};
res[1053][1]=1054;
res[1053][2]=1055;
res[1053][3]=1056;
res[1036][7]=1057;
ask[1057]={12,6,15,8,3,5,9,1,7,2,0,4};
res[1057][1]=1058;
res[1057][2]=1059;
res[1057][3]=1060;
res[975][7]=1061;
ask[1061]={3,9,14,0,11,7,6,1,8,5,4,13,2,16,18,10,15,12};
res[1061][1]=1062;
res[1061][3]=1063;
ask[1063]={13,8,1,2,11,4,3,6,9,7,5,0};
res[1063][0]=1064;
res[1063][1]=1065;
res[1063][2]=1066;
res[1061][4]=1067;
ask[1067]={6,5,9,2,4,7,0,11,1,3,8};
res[1067][0]=1068;
res[1067][2]=1069;
res[1061][5]=1070;
ask[1070]={11,9,5,1,0,6,7,2,3,8,13,4};
res[1070][0]=1071;
res[1070][1]=1072;
res[1070][2]=1073;
res[1061][6]=1074;
ask[1074]={2,5,1,7,8,0,3,6,4,9,11};
res[1074][0]=1075;
res[1074][1]=1076;
res[1061][7]=1077;
ask[1077]={13,6,11,9,2,1,0,8,7,5,4,3};
res[1077][1]=1078;
res[1077][2]=1079;
res[1077][3]=1080;
res[1061][8]=1081;
ask[1081]={13,8,0,6,3,11,1,5,4,7,2,9};
res[1081][1]=1082;
res[1081][2]=1083;
res[1081][3]=1084;
res[1061][9]=1085;
ask[1085]={2,5,9,1,13,8,3,0,7,4,6,11};
res[1085][1]=1086;
res[1085][2]=1087;
res[1085][3]=1088;
res[1061][10]=1089;
res[1061][11]=1090;
res[975][8]=1091;
ask[1091]={17,3,9,0,7,8,2,1,13,6,4,12,5,16,11};
res[1091][2]=1092;
ask[1092]={9,8,3,0,5,2,14,4,1,6,7,18};
res[1092][1]=1093;
res[1092][2]=1094;
res[1092][3]=1095;
res[1091][3]=1096;
ask[1096]={8,9,11,0,3,5,12,6,4,14,7,1,2,18};
res[1096][3]=1097;
res[1096][5]=1098;
res[1096][6]=1099;
res[1096][7]=1100;
res[1091][4]=1101;
ask[1101]={18,11,12,4,14,2,9,7,3,6,1,0,5,8};
res[1101][1]=1102;
res[1101][3]=1103;
res[1101][4]=1104;
res[1101][5]=1105;
res[1091][5]=1106;
ask[1106]={6,18,9,12,3,1,7,8,4,2,0,5,14};
res[1106][1]=1107;
res[1106][3]=1108;
res[1106][4]=1109;
res[1106][5]=1110;
res[1091][6]=1111;
ask[1111]={8,18,3,0,4,6,7,9,1,5,2,11};
res[1111][0]=1112;
res[1111][1]=1113;
res[1111][2]=1114;
res[1091][7]=1115;
ask[1115]={8,3,14,6,5,2,4,0,9,1,7,18};
res[1115][0]=1116;
res[1115][1]=1117;
res[1115][2]=1118;
res[1115][3]=1119;
res[975][9]=1120;
ask[1120]={14,6,4,0,5,8,7,13,3,2,10,9,1,16,11,15};
res[1120][3]=1121;
ask[1121]={4,9,0,5,17,8,2,7,1,6,3};
res[1121][0]=1122;
res[1121][2]=1123;
res[1120][4]=1124;
ask[1124]={4,6,7,2,1,3,0,9,12,5,8};
res[1124][0]=1125;
res[1124][2]=1126;
res[1120][5]=1127;
ask[1127]={6,5,0,8,4,7,1,13,2,9,3};
res[1127][0]=1128;
res[1127][2]=1129;
res[1120][6]=1130;
ask[1130]={8,17,2,4,5,0,1,9,7,6,3};
res[1130][0]=1131;
res[1130][2]=1132;
res[1120][7]=1133;
ask[1133]={8,3,14,0,1,6,4,9,5,2,7};
res[1133][0]=1134;
res[1133][2]=1135;
res[1120][8]=1136;
ask[1136]={0,9,4,12,8,7,1,5,2,6,3};
res[1136][0]=1137;
res[1136][2]=1138;
res[975][10]=1139;
ask[1139]={18,5,9,2,3,4,7,14,8,6,13,0,1,12,11};
res[1139][1]=1140;
res[1139][2]=1141;
res[1139][3]=1142;
res[1139][4]=1143;
res[1139][5]=1144;
res[1139][6]=1145;
res[975][11]=1146;
ask[1146]={11,5,4,3,7,8,0,9,2,14,6,13,1};
res[1146][1]=1147;
res[1146][2]=1148;
res[1146][3]=1149;
res[1146][4]=1150;
res[1][12]=1151;
ask[1151]={11,8,12,5,4,15,2,10,6,13,0,3,1,7,9,14,18,19};
res[1151][4]=1152;
ask[1152]={8,5,7,0,9,4,3,1,6,13,2,12};
res[1152][0]=1153;
res[1152][1]=1154;
res[1152][2]=1155;
res[1151][5]=1156;
ask[1156]={9,3,0,2,1,7,6,4,8,12,5,13};
res[1156][1]=1157;
res[1156][2]=1158;
res[1156][3]=1159;
res[1151][6]=1160;
ask[1160]={12,17,7,10,2,8,3,0,6,14,9,4,5,1};
res[1160][1]=1161;
ask[1161]={7,3,5,13,6,4,2,9,8,0,1};
res[1161][0]=1162;
res[1161][2]=1163;
res[1160][2]=1164;
ask[1164]={14,2,5,8,3,7,6,1,4,9,0};
res[1164][0]=1165;
res[1164][1]=1166;
res[1160][3]=1167;
ask[1167]={13,7,8,2,1,6,4,0,9,5,3};
res[1167][0]=1168;
res[1167][1]=1169;
res[1160][4]=1170;
ask[1170]={13,7,0,3,4,9,6,8,2,5,1};
res[1170][0]=1171;
res[1170][1]=1172;
res[1160][5]=1173;
ask[1173]={4,2,5,8,17,0,1,9,3,7,6};
res[1173][0]=1174;
res[1173][2]=1175;
res[1160][6]=1176;
ask[1176]={4,13,3,0,7,5,6,1,8,2,9};
res[1176][0]=1177;
res[1176][2]=1178;
res[1151][7]=1179;
ask[1179]={9,5,13,0,8,6,14,2,7,1,11,3,4,15,12,10};
res[1179][3]=1180;
ask[1180]={1,0,2,3,4,6,17,8,9,5,7};
res[1180][0]=1181;
res[1180][2]=1182;
res[1179][4]=1183;
res[1179][5]=1184;
ask[1184]={7,3,17,9,1,4,2,8,6,5,0};
res[1184][0]=1185;
res[1184][2]=1186;
res[1179][6]=1187;
ask[1187]={1,7,11,5,3,8,6,0,2,9,4};
res[1187][0]=1188;
res[1187][2]=1189;
res[1179][7]=1190;
ask[1190]={4,5,17,6,0,1,8,3,2,7,9};
res[1190][0]=1191;
res[1190][2]=1192;
res[1179][8]=1193;
ask[1193]={2,12,6,9,8,0,4,3,7,5,1};
res[1193][0]=1194;
res[1193][2]=1195;
res[1151][8]=1196;
ask[1196]={12,7,9,17,5,2,6,3,1,14,8,4,0,13};
res[1196][1]=1197;
ask[1197]={4,8,9,2,6,1,12,5,0,7,3};
res[1197][0]=1198;
res[1197][2]=1199;
res[1196][2]=1200;
ask[1200]={9,0,6,4,8,7,5,10,2,3,1};
res[1200][0]=1201;
res[1200][2]=1202;
res[1196][3]=1203;
ask[1203]={6,9,7,2,4,8,5,12,3,1,0};
res[1203][0]=1204;
res[1203][2]=1205;
res[1196][4]=1206;
ask[1206]={10,8,4,6,0,7,1,5,3,9,2};
res[1206][0]=1207;
res[1206][1]=1208;
res[1196][5]=1209;
ask[1209]={0,5,2,12,7,4,1,9,3,8,6};
res[1209][0]=1210;
res[1209][2]=1211;
res[1196][6]=1212;
ask[1212]={7,6,2,1,3,9,5,0,8,11,4};
res[1212][0]=1213;
res[1212][2]=1214;
res[1151][9]=1215;
ask[1215]={10,15,12,8,7,6,9,5,14,3,0,11,1,4,13,2};
res[1215][3]=1216;
ask[1216]={9,8,6,2,4,5,1,3,0,17,7};
res[1216][0]=1217;
res[1216][2]=1218;
res[1215][5]=1219;
ask[1219]={7,1,4,6,8,5,17,2,3,0,9};
res[1219][0]=1220;
res[1219][2]=1221;
res[1215][6]=1222;
ask[1222]={6,5,2,8,4,3,7,1,9,11,0};
res[1222][0]=1223;
res[1222][2]=1224;
res[1215][7]=1225;
ask[1225]={6,9,3,2,8,0,7,5,17,4,1};
res[1225][0]=1226;
res[1225][2]=1227;
res[1215][8]=1228;
ask[1228]={5,17,2,3,6,8,0,9,1,4,7};
res[1228][0]=1229;
res[1228][2]=1230;
res[1215][9]=1231;
ask[1231]={8,7,1,0,4,6,3,5,17,2,9};
res[1231][0]=1232;
res[1231][2]=1233;
res[1151][10]=1234;
ask[1234]={17,8,15,6,1,5,2,4,3,12,9,7,0,10,11,14};
res[1234][3]=1235;
ask[1235]={7,9,0,5,1,6,8,4,2,3,12};
res[1235][0]=1236;
res[1235][1]=1237;
res[1234][4]=1238;
ask[1238]={0,9,3,2,8,1,12,6,4,5,7};
res[1238][0]=1239;
res[1238][2]=1240;
res[1234][5]=1241;
ask[1241]={6,10,0,5,2,9,4,1,3,8,7};
res[1241][0]=1242;
res[1241][2]=1243;
res[1234][6]=1244;
ask[1244]={1,4,6,9,5,7,2,13,0,8,3};
res[1244][0]=1245;
res[1244][2]=1246;
res[1234][7]=1247;
ask[1247]={8,4,11,6,2,5,0,1,3,7,9};
res[1247][0]=1248;
res[1247][2]=1249;
res[1234][8]=1250;
res[1151][11]=1251;
ask[1251]={8,9,5,2,1,0,3,6,12,11,10,4,14,7,17};
res[1251][2]=1252;
res[1251][3]=1253;
res[1251][4]=1254;
res[1251][5]=1255;
res[1251][6]=1256;
res[1251][7]=1257;
res[1][13]=1258;
ask[1258]={13,3,5,19,6,11,7,10,0,9,1,4,8,12,2,16,14,15};
res[1258][4]=1259;
ask[1259]={1,0,2,3,7,4,8,6,12,9,5,11};
res[1259][0]=1260;
res[1259][1]=1261;
res[1259][2]=1262;
res[1258][5]=1263;
ask[1263]={12,4,11,8,2,6,1,9,7,5,3,0};
res[1263][1]=1264;
res[1263][2]=1265;
res[1263][3]=1266;
res[1258][6]=1267;
ask[1267]={6,2,3,5,7,11,9,4,1,0,13,10,14,8,12};
res[1267][2]=1268;
ask[1268]={0,6,3,5,7,2,4,1,17,8,9};
res[1268][0]=1269;
res[1268][2]=1270;
res[1267][3]=1271;
ask[1271]={9,0,2,3,5,7,1,4,8,6,17};
res[1271][0]=1272;
res[1271][1]=1273;
res[1267][4]=1274;
ask[1274]={0,17,2,3,4,6,9,8,7,1,5};
res[1274][0]=1275;
res[1274][2]=1276;
res[1267][5]=1277;
ask[1277]={4,9,0,17,3,5,2,7,6,8,1};
res[1277][0]=1278;
res[1277][2]=1279;
res[1267][6]=1280;
ask[1280]={0,3,9,1,7,8,17,2,5,6,4};
res[1280][0]=1281;
res[1280][2]=1282;
res[1267][7]=1283;
ask[1283]={3,1,6,9,4,17,0,2,8,5,7};
res[1283][0]=1284;
res[1283][2]=1285;
res[1258][7]=1286;
ask[1286]={12,14,9,8,15,2,4,7,6,1,5,3,10,0,11};
res[1286][1]=1287;
res[1286][2]=1288;
res[1286][3]=1289;
res[1286][4]=1290;
ask[1290]={2,0,17,3,7,5,6,4,8,1,9};
res[1290][0]=1291;
res[1290][2]=1292;
res[1286][5]=1293;
ask[1293]={8,6,2,4,3,7,17,0,1,5,9};
res[1293][0]=1294;
res[1293][2]=1295;
res[1286][6]=1296;
ask[1296]={5,6,17,4,1,7,9,0,2,3,8};
res[1296][0]=1297;
res[1296][2]=1298;
res[1286][7]=1299;
ask[1299]={2,3,17,8,5,1,4,0,7,6,9};
res[1299][0]=1300;
res[1299][2]=1301;
res[1258][8]=1302;
ask[1302]={11,13,8,6,10,0,7,5,9,3,4,1,14,2,12};
res[1302][1]=1303;
res[1302][2]=1304;
res[1302][3]=1305;
res[1302][4]=1306;
ask[1306]={3,5,7,8,13,4,1,0,9,2,6};
res[1306][0]=1307;
res[1306][2]=1308;
res[1302][5]=1309;
ask[1309]={2,8,6,1,0,5,9,3,4,7,17};
res[1309][0]=1310;
res[1309][1]=1311;
res[1302][6]=1312;
ask[1312]={9,0,1,5,7,8,17,6,2,3,4};
res[1312][0]=1313;
res[1312][2]=1314;
res[1302][7]=1315;
ask[1315]={3,0,1,2,4,17,7,5,9,6,8};
res[1315][0]=1316;
res[1315][2]=1317;
res[1258][9]=1318;
ask[1318]={9,14,6,4,10,15,11,0,5,2,7,13,1,8,3,17};
res[1318][3]=1319;
res[1318][4]=1320;
res[1318][5]=1321;
ask[1321]={8,9,10,4,5,6,7,3,0,2,1};
res[1321][0]=1322;
res[1321][2]=1323;
res[1318][6]=1324;
ask[1324]={10,3,2,7,5,9,6,1,4,8,0};
res[1324][0]=1325;
res[1324][1]=1326;
res[1318][7]=1327;
ask[1327]={2,1,0,4,5,10,9,7,6,3,8};
res[1327][0]=1328;
res[1327][2]=1329;
res[1318][8]=1330;
ask[1330]={12,9,1,8,0,6,2,4,7,3,5};
res[1330][0]=1331;
res[1330][1]=1332;
res[1318][9]=1333;
ask[1333]={7,0,1,12,5,9,3,2,6,4,8};
res[1333][0]=1334;
res[1333][2]=1335;
res[1258][10]=1336;
ask[1336]={11,13,8,9,3,12,1,14,2,4,0,7,5,6,10};
res[1336][2]=1337;
ask[1337]={4,3,6,7,5,1,2,0,9,17,8};
res[1337][0]=1338;
res[1337][2]=1339;
res[1336][3]=1340;
ask[1340]={2,9,6,1,7,4,8,0,3,5,17};
res[1340][0]=1341;
res[1340][1]=1342;
res[1336][4]=1343;
ask[1343]={6,7,0,17,9,8,5,4,2,1,3};
res[1343][0]=1344;
res[1343][2]=1345;
res[1336][5]=1346;
ask[1346]={8,0,7,5,6,17,4,1,3,2,9};
res[1346][0]=1347;
res[1346][2]=1348;
res[1336][6]=1349;
ask[1349]={8,3,17,4,9,6,0,7,2,1,5};
res[1349][0]=1350;
res[1349][2]=1351;
res[1258][11]=1352;
ask[1352]={17,2,7,14,3,4,13,5,8,9,1,0,6};
res[1352][0]=1353;
res[1352][1]=1354;
res[1352][2]=1355;
res[1352][3]=1356;
res[1352][4]=1357;
res[1352][5]=1358;
res[1258][12]=1359;
ask[1359]={1,6,7,0,8,9,2,17,3,4,5};
res[1359][0]=1360;
res[1359][2]=1361;
res[1][14]=1362;
ask[1362]={10,12,13,19,14,0,9,15,5,3,2,6,16,18,1,17,7,8,11,4};
res[1362][5]=1363;
ask[1363]={15,1,0,2,3,8,5,7,9,11,4,6};
res[1363][1]=1364;
res[1363][2]=1365;
res[1363][3]=1366;
res[1362][7]=1367;
ask[1367]={14,10,6,4,15,2,3,0,1,5,8,7,9,11};
res[1367][2]=1368;
res[1367][3]=1369;
res[1367][4]=1370;
res[1367][5]=1371;
res[1362][8]=1372;
ask[1372]={3,5,7,4,6,1,0,2,8,11,9,12,17,15};
res[1372][1]=1373;
res[1372][3]=1374;
res[1372][4]=1375;
res[1372][5]=1376;
res[1362][9]=1377;
ask[1377]={6,8,9,5,3,7,4,1,14,0,2,10,12,13};
res[1377][1]=1378;
res[1377][3]=1379;
res[1377][4]=1380;
res[1377][5]=1381;
res[1362][10]=1382;
ask[1382]={0,1,8,4,5,6,9,2,7,12,3};
res[1382][0]=1383;
res[1382][2]=1384;
res[1362][11]=1385;
ask[1385]={6,13,9,3,7,1,0,2,8,4,5,12};
res[1385][1]=1386;
res[1385][2]=1387;
res[1385][3]=1388;
res[1362][12]=1389;
ask[1389]={0,8,4,5,6,1,7,3,9,2,13};
res[1389][0]=1390;
res[1389][1]=1391;
res[1][15]=1392;
ask[1392]={15,14,12,16,5,2,19,7,3,11,8,9,18,1,17,4,6,0,10};
res[1392][6]=1393;
ask[1393]={2,6,1,8,3,9,5,18,4,0,7,11};
res[1393][1]=1394;
res[1393][2]=1395;
res[1393][3]=1396;
res[1392][7]=1397;
ask[1397]={18,11,12,5,17,8,6,7,3,9,1,4,2,0};
res[1397][1]=1398;
res[1397][3]=1399;
res[1397][4]=1400;
res[1397][5]=1401;
res[1392][8]=1402;
ask[1402]={4,3,13,5,9,6,7,8,2,1,0,10,18,11};
res[1402][1]=1403;
res[1402][3]=1404;
res[1402][4]=1405;
res[1402][5]=1406;
res[1392][9]=1407;
ask[1407]={9,4,2,6,1,3,8,5,10,7,0};
res[1407][0]=1408;
res[1407][2]=1409;
res[1392][10]=1410;
ask[1410]={10,11,7,6,0,4,3,9,8,5,13,1,2,12};
res[1410][2]=1411;
res[1410][3]=1412;
res[1410][4]=1413;
res[1410][5]=1414;
res[1392][11]=1415;
ask[1415]={7,9,2,8,6,1,12,5,0,10,3,4};
res[1415][0]=1416;
res[1415][2]=1417;
res[1415][4]=1418;
res[1392][12]=1419;
ask[1419]={9,3,12,4,5,1,7,0,2,6,8};
res[1419][0]=1420;
res[1419][2]=1421;
res[1][16]=1422;
ask[1422]={8,6,9,1,3,4,17,0,5,2,7,10};
res[1422][1]=1423;
res[1422][2]=1424;
res[1422][3]=1425;
res[1][17]=1426;
ask[1426]={17,8,6,10,7,1,0,9,2,3,5,4};
res[1426][1]=1427;
res[1426][2]=1428;
res[1426][3]=1429;
}
int val[200005];
int get(int pos){
return val[pos] = use_machine({0, pos});
}
void get(vector<int> positions){
assert((int) positions.size() == M);
// assumption : positions[0], positions[1], positions[2] have the same value
vector<int> states;
for(int i = 0; i < (1 << M); i += (1 << T)) states.push_back(i);
int node = 1;
int asked = 0;
while((int) states.size() > 1){
assert(!ask[node].empty());
vector<int> x;
for(int u : ask[node]) x.push_back(positions[u]);
int R = use_machine(x);
asked++;
vector<int> new_states;
for(auto it : states){
int r = 0;
for(int j = 0; j + 1 < (int) ask[node].size(); j++) r += (it >> ask[node][j] & 1) != (it >> ask[node][j + 1] & 1);
if(r == R) new_states.push_back(it);
}
node = res[node][R];
assert(node != 0);
states = new_states;
}
assert(asked <= 4);
int mask = states[0];
for(int i = 0; i < (int)positions.size(); i++) val[positions[i]] = (mask >> i & 1) ^ val[positions[0]];
}
const int K = 210;
vector<int> f;
void get(int st, int en){
while(st <= en){
int rem = en - st + 1;
if(rem == 1) get(st);
else{
vector<int> positions = {f[0], st, f[1], st + 1};
int u = use_machine(positions);
val[st] = val[f[0]] ^ (u >> 1 & 1);
val[st + 1] = val[f[0]] ^ (u & 1);
}
st += 2;
}
}
int count_mushrooms(int N) {
if(N <= 226){
for(int j = 1; j < N; j++) get(j);
return count(val, val + N, 0);
}
pre();
int n = min(N, K);
vector<vector<int>> w(2);
w[0] = {0};
for(int i = 1; i < 3; i++){
get(i);
w[val[i]].push_back(i);
}
f = (int)w[0].size() > (int) w[1].size() ? w[0] : w[1];
// cerr<<f[0]<<" " << f[1] << endl;
if(n >= 2 * T - 1){
get(3, 2 * T - 1);
for(int i = 3; i <2 * T; i++) w[val[i]].push_back(i);
}
f = (int)w[0].size() > (int)w[1].size() ? w[0] : w[1];
f.resize(T);
// for()
for(int i = 2 * T; i < n; i += M - T){
int st = i, en = i + M - T - 1;
if(en < n){
vector<int> positions = f;
for(int j = st; j <= en; j++) positions.push_back(j);
get(positions);
} else{
get(st, n - 1);
}
}
int curr = n - accumulate(val, val + n, 0);
if(n == N) return curr;
vector<vector<int>> where(2);
for(int i = 0; i < n; i++) where[val[i]].push_back(i);
int i = n;
while(i < N){
int id = (int)where[1].size() > (int) where[0].size();
int R = where[id].size();
int st = i, en = min(N - 1, i + R - 1);
vector<int> positions;
for(int j = 0; j <= en - st; j++){
positions.push_back(where[id][j]);
positions.push_back(st + j);
}
int V = use_machine(positions);
if(V % 2 == 1){
if(id == 1){
where[0].push_back(positions.back());
curr++;
}
else where[1].push_back(positions.back());
} else{
if(id == 0){
where[0].push_back(positions.back());
curr++;
} else{
where[1].push_back(positions.back());
}
}
V /= 2;
if(id == 1) curr += V;
else curr += en - st - V;
i = en + 1;
}
return curr;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |