Submission #1169056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169056		Piokemon	Painting Squares (IOI20_squares)	C++20	100 / 100	28 ms	424 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> kol={1,3,7,15,31,63,127,255,511,1023,1022,1021,1019,1015,1007,991,959,895,767,510,1020,1017,1011,999,975,927,831,639,254,509,1018,1013,1003,983,943,863,703,383,766,508,1016,1009,995,967,911,799,575,126,253,507,1014,1005,987,951,879,735,447,894,765,506,1012,1001,979,935,847,671,319,638,252,505,1010,997,971,919,815,607,191,382,764,504,1008,993,963,903,783,543,62,125,251,503,1006,989,955,887,751,479,958,893,763,502,1004,985,947,871,719,415,830,637,250,501,1002,981,939,855,687,351,702,381,762,500,1000,977,931,839,655,287,574,124,249,499,998,973,923,823,623,223,446,892,761,498,996,969,915,807,591,159,318,636,248,497,994,965,907,791,559,95,190,380,760,496,992,961,899,775,527,30,61,123,247,495,990,957,891,759,494,988,953,883,743,463,926,829,635,246,493,986,949,875,727,431,862,701,379,758,492,984,945,867,711,399,798,573,122,245,491,982,941,859,695,367,734,445,890,757,490,980,937,851,679,335,670,317,634,244,489,978,933,843,663,303,606,189,378,756,488,976,929,835,647,271,542,60,121,243,487,974,925,827,631,239,478,956,889,755,486,972,921,819,615,207,414,828,633,242,485,970,917,811,599,175,350,700,377,754,484,968,913,803,583,143,286,572,120,241,483,966,909,795,567,111,222,444,888,753,482,964,905,787,551,79,158,316,632,240,481,962,901,779,535,47,94,188,376,752,480,960,897,771,519,14,29,59,119,238,477,954,885,747,471,942,861,699,375,750,476,952,881,739,455,910,797,571,118,237,475,950,877,731,439,878,733,443,886,749,474,948,873,723,423,846,669,315,630,236,473,946,869,715,407,814,605,187,374,748,472,944,865,707,391,782,541,58,117,235,470,940,857,691,359,718,413,826,629,234,469,938,853,683,343,686,349,698,373,746,468,936,849,675,327,654,285,570,116,233,467,934,845,667,311,622,221,442,884,745,466,932,841,659,295,590,157,314,628,232,465,930,837,651,279,558,93,186,372,744,464,928,833,643,263,526,28,57,115,231,462,924,825,627,230,461,922,821,619,215,430,860,697,371,742,460,920,817,611,199,398,796,569,114,229,459,918,813,603,183,366,732,441,882,741,458,916,809,595,167,334,668,313,626,228,457,914,805,587,151,302,604,185,370,740,456,912,801,579,135,270,540,56,113,227,454,908,793,563,103,206,412,824,625,226,453,906,789,555,87,174,348,696,369,738,452,904,785,547,71,142,284,568,112,225,451,902,781,539,55,110,220,440,880,737,450,900,777,531,39,78,156,312,624,224,449,898,773,523,23,46,92,184,368,736,448,896,769,515,6,13,27,54,109,219,438,876,729,435,870,717,411,822,621,218,437,874,725,427,854,685,347,694,365,730,436,872,721,419,838,653,283,566,108,217,434,868,713,403,806,589,155,310,620,216,433,866,709,395,790,557,91,182,364,728,432,864,705,387,774,525,26,53,107,214,429,858,693,363,726,428,856,689,355,710,397,794,565,106,213,426,852,681,339,678,333,666,309,618,212,425,850,677,331,662,301,602,181,362,724,424,848,673,323,646,269,538,52,105,211,422,844,665,307,614,205,410,820,617,210,421,842,661,299,598,173,346,692,361,722,420,840,657,291,582,141,282,564,104,209,418,836,649,275,550,77,154,308,616,208,417,834,645,267,534,45,90,180,360,720,416,832,641,259,518,12,25,51,102,204,409,818,613,203,406,812,601,179,358,716,408,816,609,195,390,780,537,50,101,202,405,810,597,171,342,684,345,690,357,714,404,808,593,163,326,652,281,562,100,201,402,804,585,147,294,588,153,306,612,200,401,802,581,139,278,556,89,178,356,712,400,800,577,131,262,524,24,49,99,198,396,792,561,98,197,394,788,553,83,166,332,664,305,610,196,393,786,549,75,150,300,600,177,354,708,392,784,545,67,134,268,536,48,97,194,389,778,533,43,86,172,344,688,353,706,388,776,529,35,70,140,280,560,96,193,386,772,521,19,38,76,152,304,608,192,385,770,517,11,22,44,88,176,352,704,384,768,513,2,5,10,21,42,85,170,341,682,340,680,337,674,325,650,277,554,84,169,338,676,329,658,293,586,149,298,596,168,336,672,321,642,261,522,20,41,82,165,330,660,297,594,164,328,656,289,578,133,266,532,40,81,162,324,648,273,546,69,138,276,552,80,161,322,644,265,530,37,74,148,296,592,160,320,640,257,514,4,9,18,36,73,146,292,584,145,290,580,137,274,548,72,144,288,576,129,258,516,8,17,34,68,136,272,544,65,130,260,520,16,33,66,132,264,528,32,64,128,256,512,0};

vector<int> paint(int n) {
	vector<int> labels(n + 1, 1);
	for (int x=0;x<min(10,n);x++)labels[x]=kol[0]&(1<<(9-x));
	for (int x=1;x<n-9;x++){
		labels[x+9]=kol[x]&1;
	}
	labels[n]=10;
	//for (int x:labels) cerr << x;
	//cerr << '\n';
	return labels;
}

int find_location(int n, vector<int> c) {
	for (int x=0;x<c.size();x++){
		if (c[x]==-1)return n-x;
	}
	//for (int x:c) cerr << x;
	//cerr << '\n';
	int k=0;
	for (int x=0;x<c.size();x++){
		k += c[c.size()-1-x] * (1<<x);
	}
	//cerr << "mam: " << k << '\n';
	for (int x=0;x<kol.size();x++){
		if (k==kol[x])return x;
	}
}

Compilation message (stderr)

squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

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