Submission #602453
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
const double svm_intercept[] = {0.0,0.0,-0.319021211671,-0.028327806446,-1.01652360482,0.0,-0.69081926055,0.0,-1.11427379279,-0.26304241504,0.0,0.0,-1.06825831376,0.0,-0.628493388545,0.0};
const int svm_numcoef[] = {42,55,48,62,57,66,48,25,43,45,48,56,51,70,35,48};
const int svm_coef_index[][200] = {
{892,932,1057,1083,1095,1125,1133,1159,1162,1163,1164,1197,1200,1201,1202,1233,1234,1239,1240,1261,1269,1271,1272,1276,1299,1308,1309,1313,1338,1351,1376,1422,1423,1424,1453,1462,1463,1491,1537,1576,1614,1615},
{590,772,824,825,863,900,937,939,963,976,977,1001,1039,1089,1091,1128,1129,1166,1190,1191,1229,1242,1268,1269,1279,1280,1281,1307,1308,1318,1346,1357,1383,1384,1421,1433,1459,1466,1470,1496,1497,1504,1682,1700,1721,1737,1778,1878,1880,1881,1914,1915,1918,1952,1989},
{657,770,815,816,894,932,933,961,1046,1084,1121,1151,1157,1159,1190,1191,1196,1203,1228,1231,1267,1271,1304,1320,1356,1357,1358,1422,1460,1549,1580,1587,1614,1739,1740,1777,1816,1875,1876,1880,1881,1883,1909,1913,1917,1946,1947,1984},
{547,731,771,807,808,846,881,901,940,970,977,1009,1039,1046,1047,1083,1084,1085,1115,1152,1153,1190,1205,1226,1228,1231,1243,1244,1245,1266,1269,1270,1283,1304,1343,1381,1382,1422,1424,1425,1426,1459,1465,1501,1532,1533,1541,1570,1571,1572,1573,1576,1577,1578,1579,1614,1680,1758,1797,1835,1836,2030},
{697,737,772,774,811,848,885,1004,1008,1012,1041,1075,1078,1079,1119,1120,1129,1130,1131,1157,1158,1166,1167,1168,1205,1259,1260,1263,1298,1299,1321,1336,1347,1359,1430,1431,1467,1468,1497,1499,1504,1505,1533,1644,1682,1737,1739,1774,1776,1797,1841,1843,1844,1881,1882,1919,1920},
{551,587,589,590,657,658,659,854,892,893,894,896,897,898,899,936,964,974,975,1002,1037,1038,1040,1041,1079,1083,1084,1121,1271,1300,1308,1309,1310,1311,1312,1314,1338,1343,1344,1348,1351,1352,1378,1379,1380,1381,1390,1415,1416,1453,1454,1455,1495,1511,1571,1572,1573,1574,1578,1579,1587,1611,1612,1615,1655,1720},
{596,635,659,673,674,676,677,696,697,713,714,784,821,864,896,937,938,976,977,1007,1015,1041,1042,1044,1052,1055,1085,1094,1121,1133,1312,1339,1347,1353,1416,1438,1454,1491,1492,1493,1507,1530,1532,1611,1877,1880,1917,1918},
{701,703,704,705,742,886,904,924,929,960,966,1016,1085,1160,1198,1272,1285,1305,1309,1310,1322,1342,1348,1578,1585},
{637,855,900,903,931,1002,1013,1014,1015,1045,1051,1079,1083,1086,1187,1188,1189,1208,1224,1225,1245,1246,1305,1342,1388,1390,1416,1417,1453,1455,1461,1490,1491,1492,1499,1536,1544,1583,1613,1620,1652,1654,1658},
{591,626,630,929,931,967,968,971,997,1124,1157,1161,1162,1195,1196,1198,1269,1274,1311,1376,1383,1385,1387,1388,1422,1424,1425,1472,1473,1502,1503,1531,1533,1538,1539,1540,1541,1570,1571,1573,1574,1578,1836,1837,1884},
{516,557,822,891,899,930,1041,1042,1052,1079,1081,1112,1117,1118,1123,1124,1149,1150,1161,1162,1168,1187,1193,1199,1200,1205,1206,1231,1237,1239,1243,1269,1274,1276,1313,1344,1421,1460,1498,1509,1585,1698,1760,1883,1962,1963,2000,2038},
{433,470,507,509,510,540,543,549,810,848,885,887,888,889,921,922,923,925,927,928,962,963,965,1000,1010,1085,1086,1115,1126,1152,1153,1159,1190,1197,1228,1229,1272,1309,1347,1348,1356,1385,1386,1387,1424,1431,1432,1468,1469,1507,1610,1647,1648,1915,1950,1988},
{667,703,704,705,745,855,931,937,969,1012,1039,1042,1043,1045,1047,1081,1082,1083,1084,1085,1086,1087,1245,1284,1285,1459,1468,1497,1507,1533,1534,1540,1545,1572,1577,1578,1584,1647,1648,1654,1686,1763,1765,1766,1769,1770,1772,1803,1804,1805,1806},
{779,782,816,820,821,824,855,856,859,860,893,899,924,969,970,1007,1008,1038,1046,1052,1081,1082,1083,1084,1085,1086,1194,1195,1197,1198,1224,1225,1226,1245,1263,1279,1283,1284,1285,1306,1311,1312,1314,1315,1348,1424,1425,1426,1462,1463,1464,1508,1509,1546,1547,1616,1622,1654,1691,1692,1728,1733,1734,1735,1766,1767,1768,1802,1803,1804},
{739,740,743,822,900,1006,1082,1088,1113,1199,1238,1276,1280,1285,1303,1304,1357,1459,1496,1506,1534,1545,1546,1654,1687,1689,1692,1693,1694,1695,1723,1724,1725,1767,1843},
{482,559,598,702,703,740,779,817,861,899,974,1011,1048,1049,1085,1122,1153,1160,1191,1193,1198,1204,1243,1278,1353,1391,1422,1459,1465,1504,1541,1617,1655,1693,1695,1731,1732,1768,1769,1836,1908,1909,1910,1912,1989,2027,2065,2066}
};
const double svm_coef_value[][200] = {
{-0.0264151487547,-0.00942304513411,0.00212795644775,-0.000217858732149,0.0751716971365,-0.0642919758634,0.112063628251,-0.00242064561099,-0.0774231552679,-0.137542488274,-0.0158204739859,-0.00363748286135,-0.012557006031,-0.0757873293796,-0.246244586161,-0.26221175988,-0.0740261624555,-0.3283585484,-0.0325968946584,0.00748174326356,-0.236500595664,-0.019448190216,-0.00101093254376,-0.0349868708905,0.00766293677502,-0.0188544605616,-0.106014287461,-0.0168672687516,0.0499106928646,-0.0257987840332,0.00111589357659,-0.0484701689865,-0.00584983764033,-0.00272122998245,0.210330444066,-0.0114635807092,-0.0160962621364,0.388217629702,-0.121364006077,-0.0924921922231,-0.00264596237135,-0.0195417236991},
{0.0371995895546,0.322294979238,-0.0191653677354,-0.0350580441413,-0.171379324497,-0.045945655791,-0.0450131880773,-0.00909721595033,-0.0352194019642,-0.0202545330457,-0.0105129418983,-0.0135296086207,-0.0229445711153,-0.0427486923292,-0.0224694831817,-0.0981252808465,-0.000755878781614,-0.0552505783183,-0.0744180861363,-0.0930929769649,-0.0827960311411,-0.0782221821201,-0.0519714399423,-0.0464832386018,-0.128930462629,-0.39689847687,-0.0557912818121,-0.0035362638355,-0.175720160755,-0.0416801137943,-0.0497578703675,-0.0456054232017,-0.00317269499076,-0.0990495971416,-0.0329126294748,-0.0865539487823,-0.254066856372,0.0643659453541,-0.172868909361,-0.0183850314183,-0.13733987216,0.322945486537,0.117775761628,0.0984773991773,0.0113703640948,0.0223370148269,0.036826755294,-0.127438368293,-0.184245373151,-0.0731349970543,-0.0241920401358,-0.037016261284,-0.0159124456693,-0.0309428171261,-0.0512656457294},
{0.0719945723913,0.0404151050456,-0.0347571243916,-0.157743224539,-0.0154117893417,-0.0696328358179,-0.0894623612929,0.0166293526295,-0.528480699219,-0.0777716194756,-0.062438017745,-0.0663123303803,-0.118620734458,-0.081851655866,-0.0754339489332,-0.0487244652001,-0.0546243765464,0.0588503624053,-0.0829872133041,-0.266926755938,-0.200286203096,-0.00504812334329,-0.0692706055905,-0.0292840690444,-0.0670144039146,-0.34746960463,-0.201818900435,0.20986087482,0.148260356774,0.10856804768,-0.127984485602,0.446582748333,0.0404642568315,0.111813618913,0.0509843941769,0.0117476666576,0.134077093085,-0.0204325784714,-0.0378268364635,-0.00200336859136,-0.133890875145,-0.0128497943956,-0.0800217505926,-0.0320090733725,-0.0300563003381,-0.0292738842939,-0.0631612066515,-0.0411235456164},
{-0.107102473263,0.023257057443,0.0538861774033,0.160017344896,0.00635103126269,0.0481233505849,0.0717276759755,0.032006253763,0.00348186152723,-0.0743171450476,0.0944186218547,-0.128444601338,-0.00526710702227,-0.100002265193,-0.0171896470024,-0.0118340217621,-0.0574748263397,-0.0393618614064,-0.213114846274,-0.039650999701,-0.0957585849957,-0.0731508938231,-0.0558174888675,-0.0156404832063,-0.244780002972,0.172012680004,-0.223033485611,-0.0610666467393,-0.0523654653242,-0.388146109841,0.182508894471,0.0604607357246,-0.0837948946481,-0.0226793439273,-0.0107183227906,-0.0946188200731,-0.0683656907408,-0.0161438769755,-0.144998191555,-0.129587675512,-0.0742319947575,-0.11891849598,-0.0885514594663,-0.0881426775811,-0.115306077612,-0.0458111094989,-0.140906039191,-0.0225509698583,-0.245245567005,-0.0848792450296,-0.0499449990183,-0.0338219030352,-0.0846169651988,-0.144671907471,-0.0354965037804,-0.0519192666342,0.0454229468137,0.0909023120566,0.0100506965716,0.0769728305307,0.0487795843603,-0.0140386953801},
{-0.0161900121292,-0.0492288313303,-0.0265647898741,-0.032314834014,-0.080500464885,-0.0551590343948,-0.0253764798005,0.124270435682,0.0102638971825,0.0533107352754,0.196691272473,0.00091015436528,0.190243166308,0.145118028091,-0.160330733051,-0.149990094721,-0.032033449706,-0.0390078682572,-0.0193241875229,-0.0748536885618,-0.128206586454,-0.0273464373176,-0.181414784671,-0.0766113624023,-0.0969885328073,0.00259822073512,0.0535010330817,0.128779826089,0.0770430038698,0.217547790876,0.0946454610254,0.089956083214,0.0666472704338,0.0463196633527,0.0489700888009,0.00779840232341,0.153402266617,0.0241324538801,-0.0376905747881,-0.0261535820177,0.00743882725731,0.0269626449983,-0.0214249641957,-0.138253678134,-0.0315364613597,0.338179155724,0.0227956195591,0.0205765947396,0.0245605129827,-0.000625049442834,-0.0114945695139,-0.0932392662893,-0.0210333198658,-0.0898420489601,-0.0386775711257,-0.0153557512828,-0.0148076251059},
{-0.0171440140194,-0.00410746509983,-0.027491369254,-0.0431459218774,0.0160510233856,0.00738521610458,0.0237886907554,-0.139933854808,-0.176052259638,-0.133267047471,-0.0222155880092,-0.0182191265257,-0.0544015062361,-0.152158463461,-0.110124075909,-0.0750043552287,3.10777291476e-05,-0.0372463906479,-0.00137126952408,0.0525815933911,0.0343078907426,0.0474718148744,0.0462696302965,0.133932820484,0.105736542323,0.109962631654,0.00472604288603,0.0199822887237,-0.00779612780697,-0.0123916152576,-0.0901233977618,-0.284073501825,-0.101613302433,-0.0133717712935,-0.15199072973,-0.0294487435792,-0.0539518501795,-0.0462915018433,-0.0936697191434,-0.0442494807072,-0.0113338630855,-0.26318279178,-0.196788251274,-0.284331751824,-0.0808806138452,-0.00232954820052,-0.0319793187772,-0.00495665022875,-0.0142841813065,-0.0899627554333,-0.0750914931521,-0.186966227241,-0.0101925678495,0.111141146736,-0.0473200322125,-0.056341483357,-0.0435252555097,-0.00936337776797,-0.00415837768909,-0.0388343629691,0.192085270143,-0.025927220351,-0.0494018964293,-0.0651476835452,-0.00130566484402,0.0724161983214},
{0.0043361479289,0.0997124924249,-0.0530753002267,0.123444029807,0.0389115412742,0.0121810422355,0.0281141849595,-0.0938730526602,-0.0483919235064,0.0224147298837,0.0333593239048,-0.0248116076354,-0.00495215045547,-0.119532568225,-0.040527733724,-0.00343103234998,-0.249990942776,-0.0315018973387,-0.0898694610889,-0.0266858719561,-0.15956561402,-0.018757549998,-0.0124652081765,-0.237498775238,-0.0446556550311,-0.406666454811,0.0736014706989,-0.14934427601,0.0209541721845,-0.0191765456898,-0.254506951565,0.373457139583,-0.398356881037,-0.102811797135,0.121845531976,0.0367233286569,0.142516934809,0.0898184819017,0.207573143048,0.0322940067987,-0.00348901287891,0.031159153452,0.225711062624,0.0140692384275,-0.0768785755342,-0.0347905889928,-0.0357744217454,-0.0260817118756},
{-0.0906771034561,-0.0741001631749,-0.56527766287,-0.128332159031,-0.25978353041,0.0821630027952,0.0322163198333,0.226249156705,0.102790792866,0.369536099336,0.00327407203652,0.00422099491204,-0.0649683174358,-0.10826220081,-0.161203403821,-0.18942097725,-0.014397684796,-0.05590032667,-0.205865734479,-0.295291846304,-0.0229906098467,-0.0138139440964,-0.0705172898207,0.0975255892608,-0.43653873319},
{-0.018753607545,-0.0445054751529,0.0801114905479,0.0677935391325,-0.00318664303819,0.0142134650651,0.00617514594593,0.0907136404266,0.0782628842425,-0.0245073823378,0.114672169138,0.648600183756,-0.147961549481,-0.0354793735839,-0.298361947939,-0.20075988438,-0.0253771265868,-0.0867561565786,-0.220834315591,-0.315902896707,-0.0537638161667,-0.0138033052714,0.0106455829518,0.2096904758,-0.0115504220108,-0.123640911452,0.0105966104883,0.0240313391875,0.168943309529,0.0506663304766,-0.379229100128,0.0164755745646,0.10926315408,0.438104350416,-0.0757999213703,-0.151504985621,-0.034308179803,-0.0269693308309,-0.00912100516094,-0.0111604951065,-0.0582945593264,-0.0563414581664,-0.00721690145023},
{-0.0407015596181,-0.00918472419731,-0.0231599988797,-0.0406280279655,-0.0287263186922,-0.0704876870107,-0.00831646960657,-0.0299903762662,0.057453362445,-0.0280667074673,-0.186675564634,-0.448140746478,-0.142655686113,-0.191991158978,-0.255183300338,-0.371835440973,0.0142944019361,0.0242474488532,0.26205723563,-0.0463377542614,0.353943052954,0.09645711777,0.0964998787967,0.0828985667567,0.0265765546479,0.0750888667389,0.0103484163992,0.0160350190536,0.0807892591414,-0.0458213753539,-0.214417435694,-0.0937235536932,-0.110270235362,-0.224097993816,-0.168549069221,-0.139234798578,-0.0160696870261,-0.0870893262598,-0.403937004124,-0.0485881925863,-0.0211641660534,-0.0384326144611,0.012520711344,0.0216850099192,-0.00623479959894},
{0.0076082289739,0.0182506625684,-0.013201200533,0.0757850893215,-0.23778974472,0.0129738878624,0.0857113113086,0.0728754302404,-0.0486979346795,0.0502904593697,0.00365288350543,-0.0168379715739,0.060480679382,0.101378960752,-0.11631521827,-0.0670216244886,-0.0595360600453,-0.0460915453441,-0.124215824802,-0.118247561891,-0.0964452367827,-0.0645526285388,0.00766395238958,-0.101197109975,-0.0964192957826,-0.0592339071031,-0.057520938449,0.0153041974225,-0.0533138346768,-0.138977689982,-0.214042751036,0.0383913303774,-0.177844024383,-0.0606947396777,-0.00427057052183,0.0570674215375,0.0250805138436,0.0713298513561,0.0227591934473,-0.066450832881,-0.0104155937321,-0.0976924474373,-0.00926114573018,0.054526671645,0.113923793026,0.0639821252912,0.024811759879,0.0197509133273},
{0.0970133945251,0.0475115590923,0.0476145121139,0.184115556926,0.16366133247,0.274360294674,0.0875515113025,0.00350485011666,-0.0300069640394,-0.0500873282175,-0.0969553601097,-0.0471576338381,-0.0750833291104,-0.0244857211494,-0.0173127509236,-0.105281536624,-0.131225188533,-0.0393015455513,-0.00176203344298,-0.316627957465,-0.0703143053294,-0.0515434912145,-0.015476131422,-0.0640784734936,6.53252312637e-05,0.0481128453667,0.0478175619425,-0.0109264743932,0.00939509487144,-0.0163170038911,-0.00210036458905,-0.108456614346,-0.100018113824,-0.587071710295,-0.0292249027299,-0.0226038841938,-0.144510556136,-0.0191933210027,-0.13713138513,-0.0430148076617,0.0113184548747,-0.0042486062246,-0.0361593106691,-0.0177895195459,-0.0540470071978,0.0121362085337,0.00880524215854,0.07487004381,0.118449625388,0.0169719544043,-0.0574278422494,-0.038600490557,-0.0593889584994,0.00192531111067,0.0173156843214,0.0925543070063},
{-0.190269063694,-0.0683489193904,-0.0250244432828,-0.176699368957,-0.167166734658,0.00423593033743,0.131209554401,-0.00841268853799,0.0473842819352,-0.0835677232254,-0.0876166759598,0.0192575822087,0.0258559257019,0.00942580444652,0.146958047267,0.101362749844,0.0273605797977,0.00452588258291,0.221557291537,0.504633591577,0.0327306428019,0.010892052991,0.0298108250073,0.049045382561,0.0282713086547,-0.0407363015734,-0.162851633828,-0.0464482618787,-0.178136456142,-0.000592379838287,-0.0302141742705,0.0901601819083,-0.615345468247,-0.0694428181397,0.00533763893563,0.24203470869,-0.0664172731139,-0.0499375547439,-0.0100969327305,0.363414708851,-0.558557132461,-0.0979008374419,-0.000212048737409,-0.0995848658303,-0.0594827645622,-0.00304885762273,-0.0376532211067,-0.0584087540426,-0.0387173519564,-0.119152859066,-0.0103925590815},
{-0.0818096384205,-0.0113026908888,-0.0837453375626,-0.03850207134,-0.0802116797315,-0.118596136986,-0.0847259822167,-0.0593301684253,-0.0202091493641,-0.00799937127919,-0.0666672407862,-0.0431505673936,-0.0301125659555,-0.0254633967157,-0.113786658847,-0.0162385976679,-0.0231650309658,-0.0231781377636,-0.0346287503675,-0.0595046917414,-0.0318187204068,-0.0377688377238,-0.0271828735387,-0.136539799152,-0.572146679713,-0.0297626468219,0.0461669310006,0.0419183535096,0.111191781031,0.00249031026468,0.00648459366708,0.0427467645451,0.130942599117,0.0856891675214,0.0651615389853,0.00897378773518,0.0965106442581,0.047100130938,0.00734149625237,0.0314217508348,0.0357611366448,0.130429731915,0.00756045650897,0.0339992219856,0.0269821802072,-0.164815600726,-0.0474906546302,-0.00288916743099,-0.037773153575,-0.114863367901,-0.0858900003166,-0.0345316950452,-0.0417594150354,-0.0948758854591,-0.0377824291528,-0.0340766488131,-0.0360631707904,-0.0263498443767,-0.0618847284202,-0.0617600144862,-0.014315334342,-0.0541799615268,-0.0379042251289,-0.00586484918681,-0.0369128674791,-0.0703853323924,-0.0420008903268,-0.0779390521326,-0.0751071678601,-0.164417738985},
{-0.0756817569183,-0.166352615407,-0.192532364891,-0.196794271869,-0.248982350956,0.0256622508528,0.0735179476012,-0.0131713701389,0.0379307679202,-0.147170505718,-0.0295403311404,-0.0717345006865,-0.0340146794055,-0.0289444434474,-0.00745894905454,-0.0100305841169,-0.071316089592,0.164572957873,0.0762818555857,0.110522313542,0.190806526837,0.805475213708,0.39876166314,-0.0996165590992,-0.0232897203263,-0.0478011241668,-0.0303149605826,-0.0641214730158,-0.234148636734,-0.317191592396,-0.0248453699308,-0.096996429829,-0.0314853694657,-0.105066103566,-0.179603831655},
{0.00611342108712,0.0244315999756,0.0303426765373,-0.0678567053812,-0.281274537923,-0.0328312648945,-0.0647038698643,-0.0325385570202,0.0611667774175,0.0186859959276,0.054252865754,0.0369805075796,0.145536550173,0.0764479994774,0.0660846492815,0.0289287484055,-0.0531453584686,0.0665834918588,-0.135945441965,-0.491770086598,0.0324051086778,-0.22475041447,-0.0337597946837,-0.220091098488,-0.14092180489,-0.19845927746,0.0930820094362,0.0200657154537,-0.00392685703332,-0.0411918594953,-0.00253421717993,-0.0493110230812,-0.114895897224,-0.108522704425,-0.0115737224752,-0.0505366377344,-0.0339188768759,-0.086413576547,-0.158634964012,0.00434364806031,0.0351886535532,0.152085219143,0.000626410618974,0.00984383154676,0.0535734114745,0.138565431251,0.0114365881337,0.00745194847329}
};
const int INF = (int)1e9;
const int param_R = 1;
const int param_I = 5;
const int param_nrows = 65;
const int param_ncols = 38;
const int param_ngryphs = 16;
struct UnionFind {
vector<int> data;
UnionFind(int v) : data(v, -1) {}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
bool same(int x, int y) {
return root(x) == root(y);
}
int size(int x) {
return -data[root(x)];
}
void merge(int x, int y) {
x = root(x), y = root(y);
if (x != y) {
if (size(y) > size(x))
swap(x, y);
data[x] += data[y];
data[y] = x;
}
}
};
int T, W, H;
bool B[65][9001];
bool B_next[65][9001];
int L[65][9000];
void median_filter() {
REP(i,H) REP(j,W) {
int w = 0, b = 0;
const int R = param_R;
for(int dy = -R; dy <= R; ++dy) for(int dx = -R; dx <= R; ++dx) {
int ny = i + dy;
int nx = j + dx;
if(0 <= ny && ny < H && 0 <= nx && nx < W) {
(B[ny][nx] == 0 ? w : b) += 1;
}
}
B_next[i][j] = (b > w);
}
REP(i,H) REP(j,W) B[i][j] = B_next[i][j];
}
void input() {
cin >> T >> W >> H;
REP(i, H) {
string S;
cin >> S;
REP(j, W) {
B[i][j] = (S[j] == '#');
}
}
}
int labeling() {
UnionFind unionFind(W*H);
REP(i,H) REP(j,W) {
for(int dy = -1; dy <= 1; ++dy) for(int dx = -1; dx <= 1; ++dx) {
int ny = i + dy;
int nx = j + dx;
if(0 <= ny && ny < H && 0 <= nx && nx < W) {
if(B[i][j] && B[ny][nx]) unionFind.merge(i*W + j, ny*W + nx);
}
}
}
map<int, int> labels;
REP(i,H) REP(j,W) {
if(B[i][j]) {
if(unionFind.size(i*W + j) <= param_I) {
B[i][j] = false;
}
else {
labels[unionFind.root(i*W + j)] = -1;
}
}
}
{
int n = 0;
for(auto &iter : labels) iter.second = n++;
}
memset(L, -1, sizeof(L));
REP(i,H) REP(j,W) {
if(B[i][j]) {
L[i][j] = labels[unionFind.root(i*W + j)];
}
}
return labels.size();
}
vector<vector<vector<bool>>> split_chars(int n_labels) {
vector<int> C(n_labels, 0);
vector<int> cx(n_labels, 0);
vector<int> cy(n_labels, 0);
REP(i,H) REP(j,W) {
if(L[i][j] != -1) {
++C[L[i][j]];
cy[L[i][j]] += i;
cx[L[i][j]] += j;
}
}
vector<pair<int, int>> center_sort;
REP(n,n_labels) {
cy[n] /= C[n];
cx[n] /= C[n];
center_sort.emplace_back(cx[n], n);
}
map<int, int> label_to_pos;
sort(center_sort.begin(), center_sort.end());
{
REP(i,n_labels) {
label_to_pos[center_sort[i].second] = i;
}
}
vector<vector<vector<bool>>> MB(
n_labels,
vector<vector<bool>>(
param_nrows,
vector<bool>(param_ncols, false)));
REP(i,H) REP(j,W) {
if(L[i][j] != -1) {
int pos = label_to_pos[L[i][j]];
int y = i - (cy[L[i][j]] - param_nrows / 2);
int x = j - (cx[L[i][j]] - param_ncols / 2);
MB[pos][y][x] = true;
}
}
return MB;
}
char predict(const vector<vector<bool>> &img) {
vector<double> linear(param_ngryphs);
REP(n,param_ngryphs) {
vector<double> add;
add.push_back(svm_intercept[n]);
REP(i,svm_numcoef[n]) {
int coef_index = svm_coef_index[n][i];
double coef_value = svm_coef_value[n][i];
int y = coef_index / param_ncols;
int x = coef_index % param_ncols;
add.push_back(coef_value * img[y][x]);
}
sort(add.begin(), add.end());
linear[n] += accumulate(add.begin(), add.end(), 0.0);
}
int argmax = max_element(linear.begin(), linear.end()) - linear.begin();
return "0123456789()+-*/"[argmax];
}
typedef string::const_iterator iter;
int expr(iter& p);
int term(iter& p);
int factor(iter& p);
int number(iter& p);
int expr(iter& p) {
int r = term(p);
while(true) {
if(*p == '+') {
++p;
int rs = term(p);
r += rs;
}
else if(*p == '-') {
++p;
int rs = term(p);
r -= rs;
}
else {
break;
}
}
return r;
}
int term(iter& p) {
int r = factor(p);
while(true) {
if(*p == '*') {
p++;
int rs = factor(p);
r *= rs;
}
else if(*p == '/') {
p++;
int rs = factor(p);
r /= rs;
}
else {
break;
}
}
return r;
}
int factor(iter& p) {
if(*p == '(') {
++p; // skip (
int r = expr(p);
++p; // skip )
return r;
}
return number(p);
}
int number(iter& p) {
int r = 0;
while(isdigit(*p)) {
r *= 10;
r += *p -'0';
p++;
}
return r;
}
signed main() {
input();
median_filter();
median_filter();
int n_labels = labeling();
vector<vector<vector<bool>>> chars = split_chars(n_labels);
string eq;
REP(i,chars.size()) {
eq.push_back(predict(chars[i]));
}
iter p = eq.begin();
cout << expr(p) << endl;
}
Submission Info
Judge Result
Set Name |
Case0 |
Case1 |
Case2 |
Case3 |
Case4 |
Case5 |
Case6 |
Case7 |
Case8 |
Case9 |
Case10 |
Case11 |
Case12 |
Case13 |
Case14 |
Case15 |
Case16 |
Case17 |
Case18 |
Case19 |
Case20 |
Case21 |
Case22 |
Case23 |
Case24 |
Case25 |
Case26 |
Case27 |
Case28 |
Case29 |
Case30 |
Case31 |
Case32 |
Case33 |
Case34 |
Case35 |
Case36 |
Case37 |
Case38 |
Case39 |
Case40 |
Case41 |
Case42 |
Case43 |
Case44 |
Case45 |
Case46 |
Case47 |
Case48 |
Case49 |
Case50 |
Case51 |
Case52 |
Case53 |
Case54 |
Case55 |
Case56 |
Case57 |
Case58 |
Case59 |
Case60 |
Case61 |
Case62 |
Case63 |
Case64 |
Case65 |
Case66 |
Case67 |
Case68 |
Case69 |
Case70 |
Case71 |
Case72 |
Case73 |
Case74 |
Case75 |
Case76 |
Case77 |
Case78 |
Case79 |
Case80 |
Case81 |
Case82 |
Case83 |
Case84 |
Case85 |
Case86 |
Case87 |
Case88 |
Case89 |
Case90 |
Case91 |
Case92 |
Case93 |
Case94 |
Case95 |
Case96 |
Case97 |
Case98 |
Case99 |
Case100 |
Case101 |
Case102 |
Case103 |
Case104 |
Case105 |
Case106 |
Case107 |
Case108 |
Case109 |
Case110 |
Case111 |
Case112 |
Case113 |
Case114 |
Case115 |
Case116 |
Case117 |
Case118 |
Case119 |
Case120 |
Case121 |
Case122 |
Case123 |
Case124 |
Case125 |
Case126 |
Case127 |
Case128 |
Case129 |
Case130 |
Case131 |
Case132 |
Case133 |
Case134 |
Case135 |
Case136 |
Case137 |
Case138 |
Case139 |
Score / Max Score |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
2 / 2 |
4 / 4 |
4 / 4 |
4 / 4 |
0 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
0 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
4 / 4 |
0 / 5 |
5 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
5 / 5 |
0 / 5 |
5 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
0 / 5 |
5 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
5 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
5 / 5 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
Case0 |
000.txt |
Case1 |
001.txt |
Case2 |
002.txt |
Case3 |
003.txt |
Case4 |
004.txt |
Case5 |
005.txt |
Case6 |
006.txt |
Case7 |
007.txt |
Case8 |
008.txt |
Case9 |
009.txt |
Case10 |
010.txt |
Case11 |
011.txt |
Case12 |
012.txt |
Case13 |
013.txt |
Case14 |
014.txt |
Case15 |
015.txt |
Case16 |
016.txt |
Case17 |
017.txt |
Case18 |
018.txt |
Case19 |
019.txt |
Case20 |
020.txt |
Case21 |
021.txt |
Case22 |
022.txt |
Case23 |
023.txt |
Case24 |
024.txt |
Case25 |
025.txt |
Case26 |
026.txt |
Case27 |
027.txt |
Case28 |
028.txt |
Case29 |
029.txt |
Case30 |
030.txt |
Case31 |
031.txt |
Case32 |
032.txt |
Case33 |
033.txt |
Case34 |
034.txt |
Case35 |
035.txt |
Case36 |
036.txt |
Case37 |
037.txt |
Case38 |
038.txt |
Case39 |
039.txt |
Case40 |
040.txt |
Case41 |
041.txt |
Case42 |
042.txt |
Case43 |
043.txt |
Case44 |
044.txt |
Case45 |
045.txt |
Case46 |
046.txt |
Case47 |
047.txt |
Case48 |
048.txt |
Case49 |
049.txt |
Case50 |
050.txt |
Case51 |
051.txt |
Case52 |
052.txt |
Case53 |
053.txt |
Case54 |
054.txt |
Case55 |
055.txt |
Case56 |
056.txt |
Case57 |
057.txt |
Case58 |
058.txt |
Case59 |
059.txt |
Case60 |
060.txt |
Case61 |
061.txt |
Case62 |
062.txt |
Case63 |
063.txt |
Case64 |
064.txt |
Case65 |
065.txt |
Case66 |
066.txt |
Case67 |
067.txt |
Case68 |
068.txt |
Case69 |
069.txt |
Case70 |
070.txt |
Case71 |
071.txt |
Case72 |
072.txt |
Case73 |
073.txt |
Case74 |
074.txt |
Case75 |
075.txt |
Case76 |
076.txt |
Case77 |
077.txt |
Case78 |
078.txt |
Case79 |
079.txt |
Case80 |
080.txt |
Case81 |
081.txt |
Case82 |
082.txt |
Case83 |
083.txt |
Case84 |
084.txt |
Case85 |
085.txt |
Case86 |
086.txt |
Case87 |
087.txt |
Case88 |
088.txt |
Case89 |
089.txt |
Case90 |
090.txt |
Case91 |
091.txt |
Case92 |
092.txt |
Case93 |
093.txt |
Case94 |
094.txt |
Case95 |
095.txt |
Case96 |
096.txt |
Case97 |
097.txt |
Case98 |
098.txt |
Case99 |
099.txt |
Case100 |
100.txt |
Case101 |
101.txt |
Case102 |
102.txt |
Case103 |
103.txt |
Case104 |
104.txt |
Case105 |
105.txt |
Case106 |
106.txt |
Case107 |
107.txt |
Case108 |
108.txt |
Case109 |
109.txt |
Case110 |
110.txt |
Case111 |
111.txt |
Case112 |
112.txt |
Case113 |
113.txt |
Case114 |
114.txt |
Case115 |
115.txt |
Case116 |
116.txt |
Case117 |
117.txt |
Case118 |
118.txt |
Case119 |
119.txt |
Case120 |
120.txt |
Case121 |
121.txt |
Case122 |
122.txt |
Case123 |
123.txt |
Case124 |
124.txt |
Case125 |
125.txt |
Case126 |
126.txt |
Case127 |
127.txt |
Case128 |
128.txt |
Case129 |
129.txt |
Case130 |
130.txt |
Case131 |
131.txt |
Case132 |
132.txt |
Case133 |
133.txt |
Case134 |
134.txt |
Case135 |
135.txt |
Case136 |
136.txt |
Case137 |
137.txt |
Case138 |
138.txt |
Case139 |
139.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
68 ms |
6048 KB |
001.txt |
AC |
63 ms |
5928 KB |
002.txt |
AC |
36 ms |
5980 KB |
003.txt |
AC |
36 ms |
6056 KB |
004.txt |
AC |
37 ms |
5980 KB |
005.txt |
AC |
37 ms |
6068 KB |
006.txt |
AC |
37 ms |
6072 KB |
007.txt |
AC |
37 ms |
6064 KB |
008.txt |
AC |
35 ms |
5996 KB |
009.txt |
AC |
36 ms |
6064 KB |
010.txt |
AC |
37 ms |
5980 KB |
011.txt |
AC |
38 ms |
5976 KB |
012.txt |
AC |
37 ms |
6064 KB |
013.txt |
AC |
37 ms |
6068 KB |
014.txt |
AC |
37 ms |
6068 KB |
015.txt |
AC |
38 ms |
6068 KB |
016.txt |
AC |
40 ms |
6000 KB |
017.txt |
AC |
37 ms |
6064 KB |
018.txt |
AC |
37 ms |
6068 KB |
019.txt |
AC |
37 ms |
6104 KB |
020.txt |
AC |
38 ms |
5980 KB |
021.txt |
AC |
38 ms |
6064 KB |
022.txt |
AC |
38 ms |
5996 KB |
023.txt |
AC |
37 ms |
6064 KB |
024.txt |
AC |
37 ms |
6172 KB |
025.txt |
AC |
36 ms |
6068 KB |
026.txt |
AC |
36 ms |
6068 KB |
027.txt |
AC |
36 ms |
6064 KB |
028.txt |
AC |
36 ms |
6064 KB |
029.txt |
AC |
35 ms |
5988 KB |
030.txt |
AC |
68 ms |
7348 KB |
031.txt |
AC |
70 ms |
7264 KB |
032.txt |
AC |
68 ms |
7344 KB |
033.txt |
AC |
69 ms |
7276 KB |
034.txt |
AC |
68 ms |
7344 KB |
035.txt |
AC |
91 ms |
7256 KB |
036.txt |
AC |
69 ms |
7348 KB |
037.txt |
AC |
67 ms |
7260 KB |
038.txt |
AC |
69 ms |
7348 KB |
039.txt |
AC |
69 ms |
7344 KB |
040.txt |
AC |
69 ms |
7344 KB |
041.txt |
AC |
68 ms |
7344 KB |
042.txt |
AC |
67 ms |
7344 KB |
043.txt |
AC |
68 ms |
7348 KB |
044.txt |
AC |
68 ms |
7260 KB |
045.txt |
AC |
68 ms |
7344 KB |
046.txt |
AC |
68 ms |
7348 KB |
047.txt |
AC |
67 ms |
7344 KB |
048.txt |
AC |
67 ms |
7344 KB |
049.txt |
AC |
67 ms |
7344 KB |
050.txt |
AC |
70 ms |
7344 KB |
051.txt |
AC |
69 ms |
7400 KB |
052.txt |
AC |
67 ms |
7344 KB |
053.txt |
AC |
69 ms |
7256 KB |
054.txt |
AC |
66 ms |
7280 KB |
055.txt |
AC |
65 ms |
7344 KB |
056.txt |
AC |
67 ms |
7348 KB |
057.txt |
AC |
66 ms |
7348 KB |
058.txt |
WA |
68 ms |
7348 KB |
059.txt |
AC |
61 ms |
6956 KB |
060.txt |
AC |
64 ms |
7216 KB |
061.txt |
AC |
62 ms |
7092 KB |
062.txt |
AC |
67 ms |
7216 KB |
063.txt |
AC |
61 ms |
6960 KB |
064.txt |
AC |
68 ms |
7256 KB |
065.txt |
AC |
66 ms |
7140 KB |
066.txt |
AC |
65 ms |
7092 KB |
067.txt |
AC |
62 ms |
7012 KB |
068.txt |
AC |
64 ms |
7144 KB |
069.txt |
AC |
65 ms |
7148 KB |
070.txt |
AC |
69 ms |
7344 KB |
071.txt |
AC |
69 ms |
7344 KB |
072.txt |
AC |
67 ms |
7216 KB |
073.txt |
AC |
68 ms |
7344 KB |
074.txt |
AC |
68 ms |
7348 KB |
075.txt |
AC |
69 ms |
7344 KB |
076.txt |
AC |
66 ms |
7392 KB |
077.txt |
AC |
68 ms |
7344 KB |
078.txt |
AC |
69 ms |
7348 KB |
079.txt |
AC |
68 ms |
7344 KB |
080.txt |
AC |
69 ms |
7344 KB |
081.txt |
AC |
68 ms |
7348 KB |
082.txt |
AC |
67 ms |
7344 KB |
083.txt |
AC |
70 ms |
7268 KB |
084.txt |
WA |
68 ms |
7272 KB |
085.txt |
AC |
70 ms |
7264 KB |
086.txt |
AC |
69 ms |
7280 KB |
087.txt |
AC |
69 ms |
7268 KB |
088.txt |
AC |
67 ms |
7344 KB |
089.txt |
AC |
69 ms |
7348 KB |
090.txt |
RE |
419 ms |
10988 KB |
091.txt |
AC |
173 ms |
10928 KB |
092.txt |
AC |
175 ms |
10932 KB |
093.txt |
RE |
432 ms |
10988 KB |
094.txt |
RE |
494 ms |
10952 KB |
095.txt |
AC |
179 ms |
10924 KB |
096.txt |
RE |
423 ms |
10988 KB |
097.txt |
RE |
432 ms |
10932 KB |
098.txt |
WA |
176 ms |
10932 KB |
099.txt |
RE |
434 ms |
10928 KB |
100.txt |
WA |
173 ms |
10988 KB |
101.txt |
WA |
174 ms |
10972 KB |
102.txt |
WA |
173 ms |
10932 KB |
103.txt |
WA |
172 ms |
10988 KB |
104.txt |
WA |
171 ms |
10928 KB |
105.txt |
WA |
171 ms |
10928 KB |
106.txt |
WA |
174 ms |
10992 KB |
107.txt |
WA |
173 ms |
10932 KB |
108.txt |
WA |
172 ms |
10924 KB |
109.txt |
AC |
171 ms |
10928 KB |
110.txt |
WA |
171 ms |
10932 KB |
111.txt |
WA |
173 ms |
10932 KB |
112.txt |
AC |
172 ms |
10964 KB |
113.txt |
AC |
172 ms |
10932 KB |
114.txt |
WA |
173 ms |
10992 KB |
115.txt |
AC |
171 ms |
10928 KB |
116.txt |
AC |
171 ms |
10920 KB |
117.txt |
WA |
172 ms |
10932 KB |
118.txt |
WA |
173 ms |
10988 KB |
119.txt |
WA |
171 ms |
10992 KB |
120.txt |
RE |
421 ms |
10988 KB |
121.txt |
AC |
173 ms |
10972 KB |
122.txt |
WA |
171 ms |
10968 KB |
123.txt |
AC |
173 ms |
10932 KB |
124.txt |
AC |
174 ms |
10928 KB |
125.txt |
WA |
175 ms |
10928 KB |
126.txt |
WA |
171 ms |
10984 KB |
127.txt |
WA |
173 ms |
10932 KB |
128.txt |
WA |
188 ms |
10928 KB |
129.txt |
AC |
177 ms |
10988 KB |
130.txt |
RE |
418 ms |
10932 KB |
131.txt |
WA |
172 ms |
10980 KB |
132.txt |
WA |
171 ms |
10932 KB |
133.txt |
AC |
173 ms |
10932 KB |
134.txt |
AC |
171 ms |
10928 KB |
135.txt |
WA |
178 ms |
11116 KB |
136.txt |
WA |
172 ms |
10988 KB |
137.txt |
RE |
418 ms |
10988 KB |
138.txt |
WA |
171 ms |
10920 KB |
139.txt |
AC |
172 ms |
10984 KB |