| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 263291 | eohomegrownapps | Art Class (IOI13_artclass) | C++14 | 129 ms | 6264 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 "artclass.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int size = 5;
ld variance_data[4][9][3]={{{5.2824411498991095, 4.512041944986602, 3.9877517923801165},{4.109953000317832, 3.5251639497497593, 2.583329658299319},{4.0599414166232135, 3.214454227068947, 2.8794415155533164},{3.8187459500085006, 3.1251317597985238, 2.7258797446418295},{5.06922950704298, 4.781142315342459, 4.74983918981773},{5.66371141358102, 5.039144321323099, 3.1591464054282348},{4.552949101016332, 4.231009363821283, 4.527341573779875},{3.714847573114318, 3.659962363144, 3.586130927655374},{5.222052247854811, 2.4667857932999437, 2.195731839128234}},{{2.4666536176908296, 2.0629830581356257, 1.4699639183452446},{1.8134614491475296, 1.5684693984691638, 0.8818072983426067},{2.8088787223261735, 1.384751344990176, 0.5639851297542415},{1.0898217800933587, 1.2488571281603842, 0.7112425318447758},{1.1906425279446673, 1.0783969918239458, 0.3648423723862336},{2.347189370639743, 2.1565854065971775, 0.9459288624434778},{2.771386382611378, 2.0108536416244855, 1.388484315802357},{1.4457846705182154, 1.5124429273172633, 0.5888221288145326},{0.6145636792642141, 1.151643323705573, 0.713790344764571}},{{3.2062311073378176, 2.8479766283147865, 2.3068743850201923},{2.878344657926236, 2.1459527446561135, 1.486419588355472},{5.128999298228095, 4.886277457853918, 4.5377937973625055},{3.9024059559111812, 3.5278869922642926, 2.8621613468923983},{8.405299653224864, 5.763478847727209, 2.7424069110234894},{6.215745405462986, 5.441658127797566, 3.4619415128832145},{3.501482396033763, 3.307099720154386, 1.9938890500185074},{3.3780891002544386, 3.0475888551135184, 2.3440793528469936},{2.8942531168116536, 2.1591028437950093, 2.225162606299434}},{{1.961116047798011, 1.6635217303740293, 2.1619183579759826},{1.37826102050352, 0.10263979393525541, 0.11986603621904274},{10.059198546050265, 0.07316342656532622, 0.1047580932610654},{7.015737103375655, 3.9743478868863638, 2.10202623845263},{4.155151572803573, 0.8717720808252133, 0.3275836757344511},{5.634031846478673, 2.85864290484533, 0.3806889636843724},{0.37171422518729275, 0.3395648250852788, 0.4253246408979932},{6.4184832201406214, 2.1166633126075407, 1.1391979027732329},{7.862553785381836, 5.089142971379008, 0.978894867442586}}};
ll buckets_data[4][3][256]={{{17738,12420,11426,8650,7270,6343,5553,5049,4820,4647,4534,4425,4449,4750,6469,9270,5780,6309,5525,4841,4620,4694,4475,4686,5183,5884,6494,6918,6960,6747,6292,5900,5100,4513,4086,3550,3350,2903,2823,2509,2497,2377,2222,2231,2075,2076,2050,2128,1955,2095,2258,2225,2313,2356,2407,2400,2459,2502,2357,2497,2386,2286,2280,2343,2262,2267,2323,2400,2554,2525,2568,2647,2654,2616,2603,2502,2378,2293,2161,2084,1974,1908,1928,1823,1960,2009,2094,2102,2218,2321,2492,2744,2899,2984,3108,3082,2999,2867,2623,2317,2142,1860,1600,1478,1303,1197,1074,963,889,817,877,758,767,716,724,675,660,662,635,611,621,610,605,634,627,667,655,669,696,657,705,702,691,722,715,746,753,788,837,861,972,963,1095,1232,1360,1576,1667,2082,2290,2482,2814,3054,3466,4032,4226,4408,4661,4419,4439,4021,3805,3413,3098,3102,3109,3117,2998,3284,3266,3315,3668,3691,3759,3943,3940,3871,3923,3969,4004,4009,4052,4031,4158,4180,4291,4339,4586,4617,4835,4726,4737,4538,4472,4210,3913,3592,3548,3400,3190,3200,3310,3193,3405,3780,4161,4394,4960,5424,5808,6185,6543,7082,7360,8142,8742,9957,11031,11874,12912,13655,14250,15094,16056,16868,18400,20228,22952,25051,27433,32433,33056,34924,38785,41403,43757,41939,42253,42932,45359,47048,47064,45908,41992,35624,31572,28016,28359,30443,34828,106951,33633,33286,36484,40829,40806,62020},{11652,9403,12606,18094,17392,15544,16531,12936,10069,8587,7668,6853,6291,5710,5359,4977,4886,5002,5147,5466,5905,6394,7060,7583,7677,8446,8380,8213,7623,6847,6293,5214,4423,3869,3345,3076,2914,2765,2549,2522,2349,2442,2299,2209,2278,2202,2085,2208,2283,2289,2262,2369,2482,2683,2886,3000,3176,3519,3659,4111,4500,4916,5505,6280,6992,7753,8792,9748,11363,13028,14744,15839,16383,16144,15132,13492,11303,9288,7495,6189,5182,4334,3737,3435,3185,2898,2810,2703,2596,2748,2594,2584,2481,2501,2347,2277,2229,1932,1918,1762,1591,1544,1408,1322,1262,1144,1110,1020,1059,987,894,823,863,837,850,820,817,768,833,808,743,808,891,913,949,1000,1084,1191,1166,1256,1419,1441,1629,1713,1838,1831,1900,2067,2207,2228,2338,2293,2361,2328,2345,2377,2279,2234,2182,2120,2249,2182,2170,2232,2286,2334,2477,2631,2664,2735,2918,3077,3162,3133,3455,3441,3695,3703,3821,3892,3989,3910,4128,4175,4215,4274,4424,4152,4298,4249,4129,3908,4000,3977,4092,4198,4291,4499,4603,4538,4524,4513,4474,4425,4337,4227,4042,4153,4234,4374,4421,4564,4941,5290,5506,6123,6605,6819,7283,7695,8093,8793,9789,11124,12405,13762,15812,17863,19614,21906,23671,24440,25487,26467,26811,26927,27156,27279,30201,32814,33353,32275,30669,28513,27830,27397,26604,25772,24844,25331,24896,24580,24616,23367,24975,28001,32589,104562,30964,25575,22472,19800,18504,16642,11508,5499},{66408,34341,37761,37453,28623,25505,21710,19404,15469,13159,11698,11047,10564,10066,9150,8465,8471,8569,8721,8860,8514,8348,7910,7409,7236,6696,6421,5939,5512,4987,4828,4476,4212,4000,3903,3717,3648,3686,3603,3544,3356,3359,3237,3223,3050,3237,3385,3720,4439,5414,6608,7664,8940,9910,10655,10822,10773,10271,10089,9341,9179,8723,8198,7544,7269,6829,6263,6117,5721,5224,4719,4021,3207,2658,2123,1734,1508,1429,1277,1207,1191,1190,1167,1128,1116,1114,1130,1111,1104,1065,1105,1071,1063,1138,1006,1065,1021,1113,1065,1117,1096,1012,1167,1132,1087,1136,1050,1117,1040,1099,1110,1130,1140,1080,1114,1184,1214,1220,1305,1295,1353,1370,1377,1466,1386,1289,1280,1249,1263,1303,1218,1251,1279,1276,1297,1309,1388,1384,1370,1389,1439,1387,1366,1305,1324,1406,1350,1522,1483,1479,1589,1599,1643,1744,1727,1812,1776,1899,1996,2027,1990,1905,2011,2002,2022,2068,2195,2295,2430,2552,2680,2841,2949,3252,3461,3756,3997,4228,4610,4911,5092,5459,5672,6004,6248,6289,6423,6312,6322,6206,5918,5931,5638,5684,5501,5458,5534,5499,5592,5591,5740,5944,5981,6164,6249,6428,6540,6692,6918,7033,7317,7530,8089,8437,8899,9541,10192,11262,12758,13982,15998,17765,19637,20869,22087,24363,27430,30000,33487,35346,36590,35350,34216,33870,33008,33866,34704,34993,34540,32145,28340,24379,21293,19571,20145,20623,21349,22960,89979,11898,7495,5259,3495,2614,1131,2827}},{{2991,1971,2319,2733,3420,4172,4997,5651,6295,6750,6871,6954,7020,6764,6940,6601,6718,6804,6740,6883,7018,7048,7071,7143,7407,7395,7513,7526,7916,7959,8099,8308,8468,8519,8656,8878,9004,9188,9167,9662,9686,9632,9860,10088,10246,10211,10466,10508,10699,10772,10743,11205,11302,11420,11514,11622,11586,11530,11730,11575,11566,11684,11796,11668,11669,11470,11657,11573,11441,11650,11451,11451,11456,11497,11288,11406,11378,11398,11210,11411,11277,11297,11036,11027,11114,10871,11072,10901,10773,10665,10376,10370,10423,10282,10299,10027,9867,10013,9796,9852,9638,9657,9537,9659,9442,9401,9453,9154,9091,9133,9206,9114,8953,8826,8791,8722,8615,8539,8729,8435,8534,8567,8459,8353,8387,8332,8151,8286,8277,8274,8185,8110,7917,7983,7698,7910,7785,7791,7641,7546,7567,7563,7520,7404,7519,7387,7241,7257,7072,7073,7047,7060,6871,6812,6848,6725,6711,6672,6464,6521,6424,6354,6378,6278,6127,6239,5831,5931,5844,5678,5441,5313,5370,5308,5258,5149,5148,5080,5106,5184,5158,5121,5208,5161,5310,5280,5305,5435,5442,5417,5321,5399,5375,5469,5196,5226,5254,5274,5151,5059,5090,4982,5033,4900,4869,4841,4693,4670,4470,4327,4107,4046,3633,3511,3278,2960,2848,2586,2393,2215,1952,1886,1708,1544,1438,1340,1196,1130,1019,987,890,822,897,721,663,710,699,611,580,706,585,557,635,532,691,526,606,780,928,1113,1585,1573,1908,2344,2532,5145},{2325,2366,2998,3221,3388,3377,3416,3401,3430,3447,3605,3731,3782,3821,3969,4312,4548,4970,5485,5942,6683,6969,7262,7554,7990,7895,7912,7975,7991,7737,8084,7934,7997,7928,8017,8014,8021,8093,8155,8191,8340,8258,8424,8553,8931,8866,9016,9034,9147,9545,9537,10084,9944,10004,10327,10380,10831,10969,11386,11387,11598,11882,12078,12253,12528,12772,12751,13210,13123,13349,13757,13768,13789,14032,14330,14115,14420,14018,14434,14534,14629,14323,14484,14301,14416,14482,14335,14113,14048,14043,14182,14075,13985,13984,14144,13799,13792,13752,13507,13504,13397,13350,13004,12804,12586,12340,12311,12181,12008,11807,11520,11568,11142,11180,10897,10623,10447,10222,10216,9862,9799,9517,9489,9134,8992,8944,8808,8842,8562,8422,8368,8070,8033,7790,7562,7537,7405,7273,7204,7028,6826,6544,6601,6454,6376,6170,6004,6134,6076,5944,5829,5713,5686,5767,5477,5434,5320,5211,5153,5084,5263,5034,5071,5342,5241,5302,5313,5271,5618,5618,5766,5781,6083,6304,6517,6573,6815,7031,7304,7302,7210,7140,7080,6694,6407,6224,5902,5589,4882,4473,4200,3802,3664,3527,3407,3175,3244,3188,3087,3063,2920,2793,2542,2282,2198,2100,1937,1887,1754,1781,1722,1715,1658,1531,1598,1636,1577,1651,1564,1513,1523,1416,1335,1184,1050,965,848,747,639,517,471,370,278,227,160,105,99,67,66,58,44,39,36,35,30,27,29,27,11,18,13,24,17,13,15,46},{9948,3650,4272,4856,5598,6407,7134,8142,9042,10069,10818,11797,12969,13903,14874,15988,16918,18023,18588,19374,20003,20895,20973,21456,21567,22239,22477,22818,23250,23719,23891,24263,24398,24907,24782,25230,25170,25100,25227,24567,24532,23942,23731,23218,22417,21949,21447,21217,20581,19585,19167,18558,18050,17502,16835,16478,16123,15542,14753,14422,14262,13808,13449,12911,12491,11946,11884,11470,11289,11037,10535,10291,9838,9757,9484,8946,8846,8593,8528,8067,7766,7639,7671,7277,7036,6963,6757,6577,6309,6092,5894,5824,5477,5378,5347,5167,4892,4719,4709,4446,4470,4283,4096,3982,3980,3769,3664,3593,3433,3423,3429,3280,3232,3254,3135,3100,3165,2979,3051,2933,2959,2993,3012,3070,3084,3046,3019,3096,2971,3150,3023,3045,3250,3080,3270,3124,3240,3187,3142,3145,3287,3148,3275,3353,3238,3263,3332,3188,3139,3228,3209,3358,3360,3384,3518,3458,3437,3397,3397,3302,3205,3191,3161,3036,2910,2948,2903,2836,2868,2873,2975,2982,3020,3069,3059,3082,3042,3125,3176,3059,2872,2790,2587,2485,2273,2248,1988,2036,1683,1691,1540,1429,1373,1328,1206,1197,1111,1036,1032,946,1022,1047,978,1021,1110,1185,1262,1259,1317,1448,1448,1614,1704,1782,1908,1896,1986,1973,2113,1975,1951,1878,1764,1569,1475,1311,1100,910,721,536,402,267,201,122,79,54,38,24,13,5,3,5,0,0,0,0,0,0,1,0,0,0,0,0,0,1}},{{605,524,394,726,839,854,971,1095,1109,1148,1334,1384,1441,1533,1501,1612,1701,1752,1823,1795,1918,1950,1996,2156,2154,2280,2350,2426,2569,2681,2753,3051,3287,3252,3595,3810,3991,4060,4271,4299,4550,4572,4693,4794,4736,4904,4942,5019,4992,5015,5012,5068,5052,5198,5201,5100,5062,5253,5253,5160,5096,5159,5206,5147,5412,5194,5265,5247,5375,5439,5420,5418,5385,5489,5549,5561,5449,5652,5735,5746,5692,5751,5744,5888,5825,5742,5766,5785,5847,5916,5909,5840,5730,5682,5852,5712,5897,5947,5786,5759,5687,5686,5610,5697,5822,5718,5712,5627,5643,5768,5769,5865,5849,5766,5851,5785,5763,5781,5806,5728,5966,5710,5811,5848,5736,5823,5768,5771,5753,5775,5725,5653,5696,5776,5738,5707,5694,5646,5566,5787,5660,5592,5426,5589,5521,5501,5585,5391,5424,5494,5501,5521,5476,5449,5505,5441,5354,5434,5423,5465,5491,5468,5407,5531,5486,5470,5391,5398,5500,5385,5360,5467,5498,5422,5460,5450,5489,5415,5428,5590,5502,5378,5552,5623,5580,5551,5413,5623,5710,5496,5698,5407,5502,5494,5491,5572,5418,5483,5369,5458,5397,5383,5439,5388,5549,5578,5365,5456,5418,5487,5531,5335,5443,5433,5581,5420,5320,5307,5450,5522,5453,5560,5615,5551,5683,5522,5634,5584,5724,5718,5661,5708,5870,6046,6131,6065,6267,6536,6612,6706,6985,7011,7042,7135,7012,7100,7174,7434,7611,7612,8057,8019,8388,8309,7793,28730},{1850,1195,1065,1037,1167,1282,1367,1454,1516,1659,1699,1836,2005,2054,2223,2260,2349,2525,2586,2751,2813,2903,3021,3209,3387,3406,3490,3792,3750,3745,3961,4022,4172,4104,4343,4370,4440,4381,4492,4529,4583,4656,4678,4739,5007,4882,4925,4868,4978,4862,5126,5182,5089,5260,5118,5374,5319,5159,5408,5403,5305,5422,5520,5605,5565,5653,5460,5615,5712,5682,5898,5940,5848,6003,6052,6075,6239,6261,6267,6386,6497,6416,6389,6653,6480,6610,6540,6631,6697,6750,6793,6803,6825,6864,7083,7033,6997,7065,6903,7020,6992,7026,7065,7121,7153,7293,7293,7320,7458,7520,7378,7302,7339,7352,7323,7097,7095,6851,6859,6897,6875,6924,6722,6551,6619,6595,6565,6467,6357,6289,6222,6406,6127,6286,6169,6231,6068,6150,5957,6159,6041,5942,6064,5974,5976,5919,6009,5815,5708,5908,5811,5750,5689,5630,5680,5728,5638,5617,5485,5533,5597,5430,5527,5431,5412,5410,5401,5470,5316,5334,5232,5272,5333,5379,5270,5395,5323,5372,5381,5344,5232,5324,5396,5325,5303,5239,5304,5204,5311,5202,5163,5222,5078,5040,5068,4978,5023,4999,5047,4865,4915,4900,4935,4730,4786,4650,4805,4691,4830,4696,4659,4798,4814,4705,4695,4769,4809,4741,4629,4665,4709,4879,4786,4714,4891,4943,4822,5031,4885,5032,5267,5316,5506,5352,5612,5786,5854,6012,6065,6315,6229,6414,6522,6485,6443,6158,5892,5276,4850,3975,3046,2285,1711,1356,1216,1918},{25554,4526,4815,5023,5194,5235,5192,5128,5082,4892,4902,4823,4810,4870,4906,4847,4825,4718,4765,4760,4634,4702,4663,4676,4672,4567,4709,4752,4667,4641,4736,4702,4797,4898,4970,4899,5214,5126,5214,5256,5275,5196,5388,5393,5425,5407,5559,5349,5493,5660,5558,5646,5667,5599,5616,5752,5737,5802,5739,5992,5812,5886,6010,5944,6138,6069,6206,6048,6340,6254,6123,6284,6366,6417,6526,6460,6432,6372,6503,6422,6578,6773,6602,6593,6659,6655,6668,6792,6854,6777,6901,7101,6698,6944,6992,7000,7089,7024,7161,7157,7201,7188,7092,7234,7114,7130,7303,7289,7292,7356,7220,7292,7271,7162,7286,7383,7104,7204,7234,7286,7135,7178,7211,7173,7059,7162,7011,7109,7018,7019,7002,6858,6715,6678,6728,6704,6657,6502,6519,6532,6399,6466,6501,6240,6296,6250,6256,6147,6110,6063,6225,6175,5971,5909,5890,5847,5934,5883,5739,5649,5758,5702,5630,5505,5557,5642,5350,5472,5441,5583,5506,5403,5328,5423,5280,5162,5219,5158,5083,5100,4981,5015,5103,5028,4808,4813,4829,4967,4838,4740,4754,4873,4765,4921,4694,4751,4597,4860,4872,4987,4892,4798,4976,5001,4965,4972,4908,4993,4847,4976,4865,4823,4556,4461,4321,4135,3716,3677,3380,3202,2860,2806,2585,2484,2415,2320,2173,2280,2055,2003,1979,1730,1574,1472,1307,1274,1113,1009,963,951,847,754,739,700,574,490,508,419,377,321,278,289,186,244,112,541}},{{113,203,286,401,1146,2683,1393,431,269,265,410,623,631,969,1975,3389,4563,4275,4549,4326,6033,6916,6759,6023,5217,5517,5916,6667,7260,8892,8769,8605,8965,8867,9323,9055,9318,9231,8117,6905,5800,5003,5397,6717,7047,6179,6515,6867,7395,7358,7697,7634,7353,8154,7925,7253,6905,6311,6461,5695,5007,4340,3871,3614,3450,3211,3149,3380,3222,3021,3021,2928,3102,3337,3293,3048,3081,3032,2953,2980,3074,3159,3601,3726,3377,3364,3432,3236,3418,3580,3642,4043,4766,5330,5865,6290,6201,6007,6067,5889,5439,5309,4855,4305,3797,3413,3008,2299,1944,1564,1286,946,763,594,455,442,402,354,314,212,182,204,203,191,169,186,168,171,159,154,187,174,176,171,203,198,200,195,201,207,216,258,261,258,283,312,351,360,424,539,592,710,871,964,1136,1299,1536,1730,1972,2244,2785,3888,4811,5775,6386,7205,8493,9207,10381,10361,9701,8582,7657,7660,7680,8187,9743,10811,11475,10417,8460,8151,7215,6598,6205,6550,6652,7324,8352,9513,10940,12428,14613,14971,15366,15084,12581,11175,9145,7560,6335,5616,5136,4677,4558,4505,4634,5213,5933,6724,11208,15939,12564,8918,14063,14732,16877,17398,14889,14672,14407,14635,16275,17473,16391,16052,15592,15881,15657,17381,17808,18543,14361,10821,7981,5755,4781,4225,3871,3696,3618,3629,3532,3707,3697,3695,3766,3777,4073,4385,4895,5595,7856,12747,21121,38898},{17198,24194,21721,14677,11321,9300,5666,3539,2683,2017,1757,1650,1630,1799,2555,2991,3538,3425,4093,5232,8098,13691,21180,26482,28102,26215,22096,18058,15792,14482,13580,13040,11199,9946,9463,9367,8644,7676,7756,7175,6955,6293,6509,6311,6642,6139,6071,5612,5742,6453,8550,9252,9504,8795,8729,9457,9674,9806,10268,8860,7860,7154,8875,8562,7707,7834,7097,5674,5378,6666,7538,8656,9989,10387,8985,7904,7987,7531,7120,6559,6134,5751,4582,4312,4225,3696,3220,3077,2513,2500,2591,2694,2891,2992,3740,6156,6568,8981,9978,11711,13933,14268,15319,15368,13450,11622,8654,7723,6391,5677,5254,4999,5031,4921,4818,4908,5033,5082,5337,5476,6122,6191,6510,6112,6663,6751,7066,8760,9153,8149,5648,4469,3316,3079,3136,3178,3281,3222,3379,3425,3365,3506,3455,3677,3830,3862,3973,4009,4115,4122,4203,4110,4005,4092,4055,4114,4104,4059,4157,4144,4126,4238,4414,4620,4892,4675,4976,4981,4623,4418,4168,3733,3451,3288,3275,3603,3611,3920,4379,5141,6295,6296,6135,5935,5810,5814,6135,6360,6190,6193,5811,5357,4992,4679,3804,3253,2805,2415,2092,1850,1770,1529,1263,1112,934,765,647,545,453,367,334,291,323,308,294,283,319,307,304,311,345,392,440,445,456,448,469,500,571,573,596,621,622,673,662,652,686,672,686,670,754,749,799,774,882,1012,1093,1268,1439,1699,2063,2687,3946,7924,19725,27539},{50276,36559,31334,26167,22946,28549,31441,34324,28140,24265,25679,19210,18470,16406,15251,14016,12186,11025,12401,13507,15625,16794,17622,17148,15954,15924,16528,17167,17229,16270,13620,10942,8802,8323,7609,8385,6294,5552,5923,7850,7798,8573,6589,6003,6497,7149,6699,7872,7088,8878,11742,12830,13284,14035,15422,15757,15031,14620,13032,12069,10606,10655,10880,12325,14046,16065,13067,11770,9109,7629,7196,7059,6913,6059,6756,6317,6137,5947,5586,5293,4909,5040,4682,4566,4452,4483,4647,4530,4450,4344,4187,3922,3830,3883,3709,3737,3743,3553,3477,3099,2844,2632,2506,2400,2299,2200,2216,2174,2036,2037,1935,1954,1960,1940,2036,2089,1988,1795,1642,1497,1367,1379,1503,1761,1550,1969,2200,1497,1602,1578,1142,1021,1346,1030,1063,1004,957,1182,1195,1216,1508,1790,2095,2332,2602,3061,3368,4106,4782,6386,7692,8971,9726,10796,10708,9410,6667,4982,4039,3245,2798,2557,2315,1892,1650,1476,1420,1310,1379,1276,1474,1548,1497,1422,1456,1335,1269,1176,1116,1133,1091,900,932,870,854,877,747,974,781,993,1123,796,947,1023,935,1156,974,1240,1206,1030,978,1151,823,1442,678,1609,1464,799,1021,1223,717,1343,506,1556,533,1685,1383,624,914,560,644,745,546,1089,797,462,640,541,484,625,422,928,389,1115,1007,519,571,677,513,932,487,1144,1262,1008,786,1437,548,1769,478,2546,997,637,186,515,39,211}}};
ll sizes[4] = {2063500, 1757000, 1333500, 1473000};
ld variance(ld sx, ld sxx, ll w, ll h){
ll n = w*h;
return (sxx-(sx*sx)/(n))/(n-1);
}
vector<vector<bool>> visited;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int w,h;
int thresh = 10;
int wthresh = 200;
int bthresh = 20;
int bfs(int sx, int sy, int r[500][500], int g[500][500], int b[500][500]){
//cout<<x<<' '<<y<<'\n';
queue<pair<int,int>> q;
q.push({sx,sy});
int c = 0;
visited[sx][sy]=true;
c++;
while (q.size()>0){
auto f = q.front();
q.pop();
int x=f.first; int y=f.second;
for (int i = 0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
if (!(0<=nx&&nx<w&&0<=ny&&ny<h)){continue;}
if (visited[nx][ny]){continue;}
int delta = abs(r[ny][nx]-r[y][x])+abs(g[ny][nx]-g[y][x])+abs(b[ny][nx]-b[y][x]);
//cout<<delta<<' '<<thresh<<'\n';
if (delta>thresh){continue;}
visited[nx][ny]=true;
c++;
//cout<<"added "<<x<<' '<<y<<'\n';
q.push({nx,ny});
}
}
//cout<<c<<'\n';
return c;
}
int style(int H, int W, int r[500][500], int g[500][500], int b[500][500]) {
//r=R;g=G;b=B;
w=W;h=H;
visited.assign(w,vector<bool>(h,false));
//cout<<"processing\n";
//cout<<"cnt: "<<vcnt<<'\n';
ld variances[3] = {0,0,0};
ld buckets[3][256]={{0},{0},{0}};
int cnt = 0;
for (int y = 0; y<h-size; y++){
for (int x = 0; x<w-size; x++){
buckets[0][r[y][x]]++;
buckets[1][g[y][x]]++;
buckets[2][b[y][x]]++;
cnt+=1;
int sx[3]={0,0,0};
int sxx[3] = {0,0,0};
for (int ya = y; ya<y+size; ya++){
for (int xa = x; xa<x+size; xa++){
sx[0]+=r[ya][xa];
sxx[0]+=r[ya][xa]*r[ya][xa];
sx[1]+=g[ya][xa];
sxx[1]+=g[ya][xa]*g[ya][xa];
sx[2]+=b[ya][xa];
sxx[2]+=b[ya][xa]*b[ya][xa];
}
}
for (int i = 0; i<3; i++){
variances[i]+=variance(sx[i],sxx[i],w,h);
}
}
}
ld pcnt = 0;
ll p = 0;
ll whitecnt = 0;
ll blackcnt = 0;
for (int y = 0; y<h; y++){
for (int x = 0; x<w; x++){
if (!visited[x][y]){
pcnt+=bfs(x,y,r,g,b);
p++;
}
if (r[y][x]>wthresh&&g[y][x]>wthresh&&b[y][x]>wthresh){whitecnt++;}
if (r[y][x]<bthresh&&g[y][x]<bthresh&&b[y][x]<bthresh){blackcnt++;}
}
}
//cout<<blackcnt<<'\n';
//cout<<"twothree "<<pcnt/p<<'\n';
bool istwoorthree = (pcnt/p)<=5;
if (!istwoorthree){
if (blackcnt<50){
return 4;
}
if (whitecnt>100000){
return 1;
}
if (whitecnt<50){
return 4;
}
} else {
if (whitecnt<50){
return 2;
}
if (whitecnt>100000){
return 3;
}
}
//cout<<"cnt: "<<(pcnt/p)<<'\n';
for (int c = 0; c<3; c++){
variances[c]/=(h-size)*(w-size);
}
//cout<<"computed\n";
ld losses[4]={0.0,0.0,0.0,0.0};
for (int i = 0; i<4; i++){
for (int j = 0; j<9; j++){
for (int k = 0; k<3; k++){
ld diff = variance_data[i][j][k]-variances[k];
losses[i]+=diff*diff;
}
}
}
/*for (int i = 0; i<4; i++){
cout<<losses[i]<<' ';
}cout<<'\n';*/
ld minloss = 1e18;
int minind = -1;
ld n = w*h;
ld bucketlosses[4]={0.0,0.0,0.0,0.0};
for (int i = 0; i<4; i++){
ld loss = 0;
for (int j = 0; j<3; j++){
for (int k = 0; k<256; k++){
ld diff = (ld(buckets_data[i][j][k])/sizes[i])-(buckets[j][k]/n);
loss+=diff*diff;
}
}
bucketlosses[i]=loss;
}
if (istwoorthree){
//return (whitecnt)
return (bucketlosses[1]<bucketlosses[2])?2:3;
} else {
return (bucketlosses[0]<bucketlosses[3])?1:4;
}
//return minind+1;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||