Submission #1242073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242073		hiikunZ	Painting Squares (IOI20_squares)	C++20	100 / 100	27 ms	424 KiB

squares

#include "squares.h"
#include <vector>

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

int find_location(int n,std::vector<int> c) {
	//for(ll i = 0;i < 10;i++)cout << c[i];
	//cout << endl;
	if(c.back() == -1){
		ll cnt = 0;
		while(c[(ll)c.size() - 1 - cnt] == -1) cnt++;
		return n - 10 + cnt;
	}
	else{
		ll a = 0;
		for(ll j = 0;j < 10;j++){
			a *= 2;
			a += (c[j] == 1);
		}
		return ans2[a];
	}
	return 0;
}

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