Submission #1169288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169288		bbartek	Painting Squares (IOI20_squares)	C++20	0 / 100	31 ms	436 KiB

squares

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back
#include "squares.h"

const int maxkod = 1e6;
int malowanie[] = {0,1,1,0,1,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,0,1,1,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,0,1,1,0,0,0,1,0,1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,0,1,1,1,0,0,0,1,1,0,1,0,0,0,1,1,0,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,1,1,0,0,0,1,0,0,1,1,0,1,1,1,0,0,1,1,1,1,0,0,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,0,0,0,1,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,1,1,0,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,1,0,1,0,0,0,0,1,0,0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,1,0,1,0,0,0,1,1,1,0,1,0,0,1,1,0,1,1,0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,1,0,1,0,1,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,1,1,0,1,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,1,0,0,0,1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,0,1,1,0,0,1,0,0,1,1,1,0,0,1,1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,0,1,0,1,1,1,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,0,1,0,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1,1,1,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,0,1,1,1,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,1,0,0,1,1,1,0,0,0,0,1,1,0,0,1,0,1,0,1,0,1,1,0,0,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,0,1,1,1,0,1,0,0,1,1,0,0,0,1,0,0,1,1,1,0,0,1,0,1,0,0,1,0,1};
int kody[] = {0,30955,15477,7738,20253,10126,21447,10723,21745,27256,30012,15006,7503,3751,1875,17321,25044,12522,22645,27706,30237,31502,32135,16067,24417,12208,22488,27628,13814,6907,3453,18110,25439,12719,22743,11371,22069,11034,21901,27334,13667,6833,3416,18092,9046,20907,26837,13418,6709,3354,18061,25414,12707,22737,27752,30260,15130,7565,20166,26467,29617,31192,31980,32374,32571,32669,16334,8167,4083,2041,17404,25086,28927,14463,7231,3615,1807,903,16835,24801,28784,30776,15388,7694,20231,26499,29633,31200,15600,7800,3900,1950,975,487,243,16505,24636,12318,22543,27655,30211,15105,23936,11968,22368,11184,21976,27372,30070,15035,23901,11950,5975,19371,9685,4842,2421,17594,25181,28974,14487,7243,20005,26386,13193,6596,19682,26225,13112,6556,19662,9831,21299,10649,21708,10854,21811,27289,30028,15014,7507,3753,18260,25514,29141,30954,31861,32314,16157,24462,28615,30691,15345,24056,12028,22398,11199,21983,10991,21879,27323,30045,31406,15703,24235,28501,14250,23509,11754,22261,27514,30141,31454,32111,32439,16219,24493,28630,14315,23541,11770,22269,27518,30143,15071,7535,3767,18267,25517,12758,22763,11381,5690,2845,17806,25287,12643,22705,11352,22060,11030,21899,27333,30050,31409,32088,32428,16214,24491,28629,30698,31733,32250,16125,8062,20415,26591,29679,31223,15611,7805,20286,10143,5071,2535,1267,633,16700,24734,12367,6183,19475,9737,21252,10626,21697,27232,13616,23192,11596,22182,11091,21929,10964,5482,2741,1370,685,342,171,16469,24618,12309,6154,19461,26114,29441,31104,15552,7776,3888,18328,25548,12774,6387,3193,17980,8990,4495,18631,25699,12849,22808,27788,30278,15139,7569,20168,26468,29618,31193,15596,7798,20283,10141,21454,10727,5363,19065,9532,21150,26959,13479,23123,27945,30356,15178,23973,11986,5993,19380,26074,13037,6518,3259,1629,17198,24983,12491,6245,19506,9753,4876,2438,1219,16993,8496,20632,26700,13350,6675,3337,18052,9026,4513,2256,1128,564,16666,8333,20550,26659,29713,14856,7428,3714,1857,928,16848,24808,12404,6202,3101,17934,8967,20867,26817,13408,23088,11544,22156,27462,13731,23249,11624,22196,27482,30125,15062,23915,11957,5978,19373,9686,21227,26997,13498,23133,11566,5783,2891,17829,25298,29033,14516,7258,20013,10006,21387,10693,5346,2673,1336,17052,8526,4263,2131,17449,8724,20746,26757,29762,14881,7440,20104,10052,5026,18897,25832,12916,22842,11421,22094,27431,30099,31433,32100,16050,8025,20396,10198,21483,10741,5370,19069,25918,12959,6479,3239,18003,9001,4500,2250,1125,562,281,16524,8262,20515,26641,29704,14852,7426,20097,10048,21408,10704,21736,10868,5434,2717,1358,17063,8531,4265,18516,25642,29205,30986,31877,15938,24353,12176,22472,11236,5618,2809,1404,702,351,175,16471,8235,4117,2058,17413,8706,4353,18560,25664,12832,22800,11400,5700,2850,17809,25288,29028,14514,23641,11820,5910,19339,26053,13026,22897,27832,13916,6958,19863,9931,4965,2482,17625,8812,20790,26779,29773,31270,15635,24201,28484,30626,15313,24040,12020,22394,11197,5598,19183,9591,21179,26973,29870,14935,7467,20117,10058,5029,2514,1257,628,16698,8349,4174,2087,17427,8713,4356,2178,17473,8736,4368,18568,9284,4642,2321,1160,580,290,16529,8264,4132,2066,1033,16900,24834,12417,6208,3104,17936,25352,29060,14530,23649,11824,22296,27532,13766,6883,19825,9912,4956,18862,9431,4715,18741,9370,4685,18726,25747,29257,31012,15506,7753,20260,26514,29641,14820,23794,11897,5948,2974,17871,25319,12659,6329,3164,1582,17175,8587,4293,18530,9265,4632,2316,1158,16963,8481,20624,10312,5156,2578,1289,644,16706,24737,12368,6184,19476,9738,4869,2434,17601,25184,12592,6296,3148,1574,787,16777,8388,20578,10289,5144,2572,17670,25219,12609,6304,19536,9768,4884,18826,25797,29282,14641,7320,20044,26406,13203,6601,3300,18034,25401,12700,6350,19559,9779,4889,18828,9414,21091,26929,13464,6732,19750,26259,13129,6564,19666,9833,21300,27034,29901,31334,32051,16025,8012,4006,18387,9193,4596,2298,1149,574,287,16527,8263,4131,18449,25608,12804,6402,3201,17984,25376,29072,30920,15460,24114,28441,30604,15302,7651,3825,18296,25532,29150,14575,23671,11835,22301,11150,5575,2787,17777,8888,4444,2222,17495,8747,4373,2186,17477,8738,20753,10376,5188,18978,25873,12936,22852,11426,5713,2856,17812,8906,4453,18610,25689,29228,30998,31883,32325,32546,32657,32712,32740,32754,16377,24572,12286,22527,27647,30207,31487,15743,7871,3935,18351,9175,4587,18677,25722,29245,14622,23695,28231,30499,15249,24008,12004,6002,3001,17884,25326,29047,30907,31837,15918,7959,3979,18373,9186,20977,26872,29820,31294,15647,7823,3911,18339,25553,12776,22772,27770,13885,23326,28047,14023,23395,28081,14040,7020,19894,26331,13165,6582,19675,9837,21302,10651,21709,27238,13619,23193,27980,30374,31571,32169,32468,16234,24501,12250,6125,3062,1531,17149,24958,12479,22623,27695,30231,15115,23941,28354,14177,7088,19928,9964,4982,2491,1245,17006,8503,4251,2125,17446,25107,12553,22660,27714,13857,23312,28040,30404,15202,7601,3800,18284,9142,4571,2285,17526,25147,28957,30862,31815,15907,7953,20360,10180,5090,18929,25848,29308,14654,7327,3663,1831,17299,25033,12516,6258,19513,9756,21262,10631,21699,10849,21808,27288,13644,6822,3411,18089,9044,4522,2261,17514,25141,12570,6285,19526,26147,13073,6536,3268,18018,9009,4504,2252,1126,16947,24857,28812,14406,23587,11793,5896,19332,26050,29409,14704,7352,3676,1838,919,459,16613,24690,28729,30748,31758,32263,32515,32641,32704,32736,32752,32760,32764,32766,32767,16383,24575,12287,6143,3071,17919,25343,29055,30911,15455,7727,3863,18315,25541,29154,14577,23672,28220,30494,15247,7623,3811,18289,9144,20956,26862,29815,14907,23837,11918,5959,19363,26065,13032,6516,3258,18013,9006,4503,18635,25701,29234,14617,7308,20038,10019,21393,10696,5348,19058,9529,21148,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int numer[maxkod];

vector<int> paint(int n) {
	vector<int> kolory(n + 1);
    for(int i=0;i<n;i++){
        kolory[i] = malowanie[i+1];
    }
    kolory[n] = 15;
	return kolory;
}

int find_location(int n, vector<int> c){

    for(int i=1;i<=n;i++){
        if(i>986)
            break;
        
        numer[kody[i]] = i;
    }


    if(c[14] == -1){
        int ile = 0;
        for(int i=14;i>=0;i--){
            if(c[i]==-1)
                ile++;
        }
        //cout<<"jestem\n";
        return n-(15-ile)-1;
    }
    else{
        int akt=0;
        for(int i=0;i<15;i++){
            //cout<<c[i];
            if(c[i]){
                akt += (1<<i);
            }
        }
        /*
        cout<<"\n";
        cout<<akt<<"\n";
        */
        return numer[akt]-1;
        
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55