제출 #1169785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169785		jbareja	Painting Squares (IOI20_squares)	C++20	100 / 100	27 ms	424 KiB

squares

#include "squares.h"
#include <bits/stdc++.h>

using namespace std;

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

int val(vector<int>& vec, int l, int r=-1) {
	if (r == -1) r = l + k - 1;
	int res = 0;
	for (int i = r; i >= l; i--) {
		res *= 2;
		res += vec[i];
	}
	return res;
}

vector<int> paint(int n) {
	vector<int> ans;
	for (int i=0; i<n; i++) ans.push_back(label[i]);
	ans.push_back(k);
	return ans;
}

int find_location(int n, vector<int> c) {
	int cnt = 0;
	for (int i: c) if (i == -1) cnt++;
	if (cnt > 0) return n + cnt - k;
	int hsh = val(c, 0);
	return hsh_table[hsh];
}

// vector<int> recursive(int n, vector<int> vec, unordered_map<int, bool> M) {
// 	if (vec.size() == n) {
// 		return vec;
// 	}
// 	// add zero
// 	vec.push_back(0);
// 	int hsh = val(vec, (int)ssize(vec)-k);
// 	if (!M[hsh]) {
// 		M[hsh] = true;
// 		vector<int> vec2 = recursive(n, vec, M);
// 		if (vec2.size() == n) return vec2;
// 		M[hsh] = false;
// 	}
// 	vec.pop_back();
// 	// add one
// 	vec.push_back(1);
// 	hsh = val(vec, (int)ssize(vec)-k);
// 	if (!M[hsh]) {
// 		M[hsh] = true;
// 		vector<int> vec2 = recursive(n, vec, M);
// 		if (vec2.size() == n) return vec2;
// 		M[hsh] = false;
// 	}
// 	return {};
// }
//
// void gen_label(int n) {
// 	unordered_map<int, bool> M;
// 	vector<int> vec(min(k,n), 0);
// 	if (k >= n) {
// 		for (int i=0; i<n; i++) cout << vec[i]; cout << endl; // <========
// 		vec.push_back(k);
// 	}
// 	M[val(vec, 0)] = true;
// 	vector<int> labels = recursive(n, vec, M);
// 	labels.push_back(k);
//
// 	cout << "{";
// 	for (int i=0; i<n; i++) cout << labels[i] << ",";
// 	cout << "}" << endl;
// }
//
// void gen_hsh_table(int n) {
// 	vector<int> hsh_table(1<<k, -1);
// 	for (int i=0; i<n-k; i++) {
// 		int hsh = val(label, i);
// 		hsh_table[hsh] = i;
// 	}
// 	cout << "{";
// 	for (int i=0; i<hsh_table.size(); i++) cout << hsh_table[i] << ",";
// 	cout << "}" << endl;
// }

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