Submission #1051044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051044		rainboy	How to Avoid Disqualification in 75 Easy Steps (CEOI23_avoid)	C++17	90 / 100	1 ms	368 KiB

avoid

#include "avoid.h"
#include <vector>
//#include <iostream>

using namespace std;

const int N = 1000, LN = 10, L = 28;

typedef vector<int> vi;
typedef pair<int, int> pi;

int count(int b) {
	return b == 0 ? 0 : count(b & b - 1) + 1;
}

pi scout(int q, int b) {
	if (q == 10) {
		for (int l = 0; l < LN; l++) {
			vi ii;
			for (int i = 0; i < N; i++)
				if ((i >> l & 1) != 0)
					ii.push_back(i + 1);
			send(ii);
		}
		vi cc = wait();
		int i = 0;
		for (int l = 0; l < LN; l++)
			if (cc[l])
				i |= 1 << l;
		return { i + 1, i + 1 };
	} else if (q == 20) {
		int lower = 0, upper = N;
		while (upper - lower > 1) {
			int m = (lower + upper) / 2;
			vi ii;
			for (int i = lower; i < m; i++)
				ii.push_back(i + 1);
			send(ii);
			if (wait()[0])
				upper = m;
			else
				lower = m;
		}
		int i_ = lower;
		lower = 0, upper = N + 1;
		while (upper - lower > 1) {
			int m = (lower + upper) / 2;
			vi ii;
			for (int i = lower; i < m; i++)
				if (i != i_)
					ii.push_back(i + 1);
			if (ii.size() == 0) {
				lower = m;
				continue;
			}
			send(ii);
			if (wait()[0])
				upper = m;
			else
				lower = m;
		}
		int j_ = lower;
		if (j_ == N)
			j_ = i_;
		return { i_ + 1, j_ + 1 };
	} else {
#if 0
		srand(12345);
		vi bb(N), ij(1 << L, -1);
		for (int j = 0; j < N; j++) {
			cerr << j << endl;
			bool good = false;
			while (1) {
				bb[j] = rand() % (1 << L);
				if (count(bb[j]) != L / 3)
					continue;
				good = true;
				for (int i = 0; i <= j; i++) {
					if (ij[bb[i] | bb[j]] != -1) {
						good = false;
						break;
					}
					ij[bb[i] | bb[j]] = -2;
				}
				if (good) {
					for (int i = 0; i <= j; i++)
						ij[bb[i] | bb[j]] = i * N + j;
					break;
				}
				for (int i = 0; i <= j; i++)
					if (ij[bb[i] | bb[j]] == -2)
						ij[bb[i] | bb[j]] = -1;
			}
			for (int l = 0; l < L; l++)
				cerr << (bb[j] >> l & 1);
			cerr << endl;
			if (!good)
				return { -1, -1 };
		}
		cerr << "{ ";
		for (int j = 0; j < N; j++)
			cerr << bb[j] << ", ";
		cerr << "}";
		return { -1, -1 };
#endif
		int bb[N] = { 55116225, 84040769, 134943366, 84509284, 84976916, 169022498, 29500472, 1754125, 75796936, 70584361, 107352100, 71330992, 67316357, 138854442, 19006069, 36078611, 8401455, 69606920, 180650561, 138153344, 68365346, 3421206, 43266566, 11546790, 3553793, 9478251, 40143944, 42894346, 245383714, 21533062, 210903180, 240784384, 6375753, 170240016, 121741442, 210345996, 220473350, 185729252, 14231816, 201904673, 141594668, 178275969, 92868682, 21058884, 142906634, 220203545, 218712322, 71508547, 17696874, 29627744, 141185537, 16142352, 202940740, 69485394, 160434278, 159810305, 184708104, 27693344, 136743681, 135414986, 35217808, 78033024, 712967, 6554517, 206962740, 143818915, 140517993, 134595780, 171511818, 7614726, 68192461, 102802721, 34637642, 144733256, 151193172, 8942786, 57681932, 67378977, 3838600, 275851, 209834001, 60835152, 24659712, 31736100, 25920033, 67510938, 136979506, 117608594, 88082187, 76687472, 177210785, 170460488, 19284110, 71566553, 8003732, 33852613, 201870504, 102827065, 140525932, 222502945, 138806929, 15369024, 51680002, 36245016, 101880964, 109314695, 105055258, 48777504, 21301425, 8959237, 44043324, 71689280, 137370306, 6591020, 6428167, 23987203, 17395796, 76553362, 100992594, 74254408, 42226568, 4297893, 40407248, 185991320, 135874627, 42015299, 251954248, 172239044, 88174784, 201886229, 35717493, 124798016, 81903888, 207036544, 159549451, 134500698, 27328605, 143790405, 153620100, 36473000, 140083969, 33767612, 8722312, 13519008, 28049933, 36324944, 5877800, 18352207, 138514489, 4326526, 1409508, 147886276, 142659112, 104415268, 35851398, 38556992, 101721258, 4256930, 43286866, 19108288, 90213444, 68192626, 11561736, 169903344, 138691524, 21092448, 45125736, 156321026, 142082276, 63513344, 202313793, 210436768, 29927744, 17843030, 51380623, 59266057, 122292234, 161228832, 85494021, 184572419, 20106752, 42244118, 25703234, 43321992, 1425699, 137126164, 117563488, 73421105, 106107456, 139464883, 14950864, 125993184, 36353088, 119640256, 27644416, 20980441, 34219206, 140640665, 2674898, 77631668, 68164651, 64880672, 134223321, 39858772, 20252228, 168202628, 35000545, 9128005, 2524806, 37905169, 29416480, 79183921, 142636051, 114360610, 29591585, 142787210, 3807370, 50929766, 16837681, 87163925, 1919076, 10567910, 42174209, 6572089, 178782533, 44940, 2104774, 4657294, 23470657, 76573058, 13914306, 26880066, 33900934, 68704452, 39113856, 36135232, 4295889, 28328609, 17446937, 37983235, 159385058, 9609735, 235143601, 2205520, 117771012, 261096001, 6021124, 19150092, 68031074, 135609600, 1079920, 147604616, 21000485, 12993697, 138170377, 176824586, 11078220, 70424320, 1790473, 43016978, 136465604, 52486529, 41225218, 85722882, 74500640, 24131856, 157311011, 87077889, 104900760, 92553491, 3453536, 33817532, 16884530, 34091661, 3320865, 171212900, 72373400, 214317, 69800716, 10695944, 50446606, 73474273, 181010470, 167872684, 4899410, 101719240, 34145705, 207644712, 149000260, 1616202, 151847181, 8508802, 13129348, 51454545, 17870083, 636552, 79726402, 79206402, 67244905, 26974208, 136368864, 3300616, 111280752, 18637089, 37803060, 46277157, 57152592, 10555955, 84154548, 170107912, 134227662, 69476724, 4285978, 8512161, 148029968, 219201606, 29370593, 39207016, 10637524, 114819154, 71594499, 67758344, 6449314, 92702224, 137494859, 62939696, 103465473, 209745, 42219844, 219955248, 84063272, 72098572, 179831329, 5051658, 71583972, 65159425, 9799749, 84421714, 226758992, 167830692, 159490580, 155252752, 11322386, 174326346, 13701212, 101741636, 3098768, 38998054, 134273330, 51712138, 24133662, 117970472, 50465326, 109586516, 144196634, 13275203, 96518228, 78512544, 52562352, 11821154, 76439812, 46440707, 62920258, 19277322, 4555062, 8414122, 203210881, 20485408, 4626184, 137119826, 20523266, 153104689, 1444435, 50618820, 179314884, 134749796, 10683810, 84230252, 11682498, 14163104, 235940004, 142706914, 4432041, 37786437, 52597012, 136107, 4869254, 26419724, 52503062, 102774432, 85472392, 219169576, 38535271, 169158722, 85994084, 33709187, 237047041, 100698517, 50367257, 29103120, 100805643, 37233204, 17060451, 73442449, 6577344, 73696644, 68125024, 109082657, 159646101, 10824228, 67537508, 201384205, 61628420, 51408945, 159453237, 174129923, 3736122, 136971036, 175136777, 5081132, 178402305, 184754691, 10880113, 1645590, 17936592, 22055128, 19184642, 762929, 201704706, 214306888, 71702577, 142657472, 33730914, 163709100, 203686989, 1102997, 134780129, 27283658, 204144905, 54541377, 180422768, 226526082, 22038147, 178783750, 85786705, 27038336, 34949145, 191107090, 201386082, 21500218, 3409209, 101875766, 69549072, 1366153, 16065025, 160980997, 202414360, 210897444, 168036038, 921296, 184567378, 65015941, 168857105, 83991088, 18894377, 110258184, 9766966, 235610242, 25297874, 73671190, 38843968, 69325380, 9312393, 105710216, 243327000, 19734752, 188746464, 59359250, 18296865, 19404550, 4769448, 21315723, 151557146, 67668390, 3843330, 19570821, 202145976, 58890756, 35854865, 68774401, 71975109, 6996360, 1101126, 34695364, 69755978, 157844104, 109216803, 134447474, 17963212, 252370944, 16866600, 17369486, 50533665, 168052237, 77127690, 6434060, 168835594, 97526913, 146909328, 209818912, 212873480, 38809956, 168325448, 34439953, 27829024, 16999812, 134578269, 25298077, 23282224, 5644900, 4248220, 144212140, 37093930, 307681, 2402712, 151196305, 25205005, 185369094, 11477512, 12369956, 260088065, 137142418, 105128998, 144196200, 135940512, 209191939, 48237665, 75516820, 110144064, 38996264, 25389320, 170350592, 5071366, 14686616, 178391233, 220344386, 138447809, 15217200, 220746756, 117477962, 138989606, 134792912, 38929976, 18284844, 212338834, 207933441, 172165189, 244582472, 1726471, 11637808, 146873473, 34833688, 398694, 147068998, 10298912, 109774992, 145063988, 102916257, 35901704, 34099735, 43520960, 159846424, 235471433, 139083008, 192991362, 92295309, 93635074, 1353877, 140910980, 20496482, 863344, 59876360, 22356272, 201414732, 2313986, 67471113, 167910273, 17191090, 105474176, 59179170, 135934256, 168133472, 67643282, 138952862, 170429698, 2236703, 137691462, 213919266, 86526482, 4308288, 55967938, 15861864, 167783717, 52441496, 151258864, 75577729, 207102497, 12863635, 39601665, 1509496, 230758912, 71139904, 2431372, 143327436, 115868744, 249692320, 3149265, 178471488, 15925794, 136224777, 76957730, 136397930, 8923737, 31786368, 90252832, 235949121, 22614029, 46533129, 85996177, 234216, 42287697, 6914325, 5317450, 100778292, 218640592, 63701522, 81977352, 23855448, 123732529, 137470033, 243795592, 50925784, 27525419, 119279636, 207725060, 61874249, 67290920, 84547008, 153764008, 12192003, 126484611, 35669263, 152241425, 60180496, 137922053, 17185952, 211946501, 76154021, 176297360, 240140673, 146907143, 28444048, 67259856, 23382148, 54872321, 111249442, 37755450, 79893648, 201477762, 54102528, 93455881, 134411297, 77205856, 353861, 134517460, 205733913, 160440632, 12597001, 153387059, 10590215, 17583684, 159518020, 187762976, 22293026, 151873664, 118629904, 9451722, 47190808, 13508692, 108006145, 71534884, 37225625, 67854386, 14734656, 17302453, 172049089, 137265414, 258539552, 8398645, 39618580, 68258837, 70404248, 141688924, 8872040, 165325, 86442072, 18141260, 213913912, 67701387, 80617481, 143729956, 36275394, 591571, 34660391, 168927491, 143739536, 35805956, 235685893, 139463310, 170430856, 203714578, 41950568, 4991034, 2970784, 51450756, 186813456, 17901703, 89408896, 101734668, 135137956, 71373158, 151826500, 7521290, 17211475, 10847274, 54612024, 4450824, 67429516, 142747360, 50858225, 88113513, 157885456, 73400, 30458020, 40140963, 26349955, 138903760, 1461269, 71866437, 7397792, 164234306, 42490392, 71844633, 159563880, 23089475, 205598857, 109158674, 9181297, 35360773, 3371042, 194643969, 34194017, 130024024, 144976514, 101255461, 134705680, 8547680, 166727686, 1491484, 14419466, 201657489, 152451074, 148903106, 117441822, 12616154, 71699973, 173017684, 29444613, 126422048, 177873424, 92414042, 156266536, 21497005, 78192808, 37032496, 27599889, 9448368, 67934729, 212343072, 803390, 118555655, 69665604, 95420476, 13943301, 59540513, 101191866, 51678244, 81798020, 86319504, 145473552, 17483281, 143475458, 291406, 76328994, 135332462, 67260503, 71049731, 173868040, 33980601, 151949329, 36176110, 213090368, 52691125, 22684448, 70648161, 11569032, 151691488, 88903716, 38799715, 76907392, 214220960, 68309541, 13470976, 177553441, 151001449, 8718877, 138546954, 151405606, 51176464, 152199376, 235733328, 185074473, 177261824, 84552204, 226820617, 126169092, 80773777, 143206922, 35729617, 37817225, 8461358, 218274112, 168972301, 22177860, 146999310, 75598664, 76170762, 21005006, 186389506, 139010480, 35921172, 96474644, 219165316, 246481936, 9756952, 140247365, 4464226, 147098648, 4740048, 226575380, 176563330, 102778006, 38283539, 139546897, 93073417, 185145392, 5517057, 229916736, 10562706, 167920977, 960384, 248021256, 67281212, 136358950, 9109655, 205613076, 372763, 14230208, 16811388, 75633182, 17021200, 251920411, 67701075, 67289627, 207643456, 84971820, 176236044, 205882408, 152052782, 68797474, 125106, 134836362, 33986864, 155520130, 82363393, 253825538, 185714704, 135795587, 151033991, 18375784, 153122432, 201655822, 113511682, 34752007, 134269148, 168878852, 59326597, 3155533, 76247104, 63114248, 205664898, 69384452, 32522832, 85149792, 136580634, 4214179, 136332854, 113250403, 15929604, 71329380, 46301454, 27857089, 12761122, 1835498, 22552839, 59769139, 69736502, 151005612, 53610144, 5381824, 189202948, 578968, 805699, 14747147, 11053444, 213940226, 40653320, 151266823, 1582876, 103072012, 25464082, 10803272, 17189704, 16933977, 68714779, 9238529, 173020264, 2646684, 120063241, 12602908, 2994241, 73498670, 134311136, 87164995, 20038401, 23103546, 34390101, 43614356, 68813272, 83956131, 1073499, 5640963, 100929942, 44639265, 170206244, 1284512, 6328553, 209740067, 36747269, 16861040, 143020832, 76192832, 236363780, 220201370, 79757560, 18912345, 72507474, 54624594, 1344760, 135217226, 72090759, 9968424, 2705188, 3297968, 117711584, 67124755, 3256334, 37245016, 136405441, 19075347, 36902980, 98648067, 177405977, 8672341, 172294298, 151931152, 8787604, 69634338, 4723279, 237273680, };
		for (int l = 0; l < L; l++) {
			vi ii;
			for (int i = 0; i < N; i++)
				if ((bb[i] >> l & 1) != 0)
					ii.push_back(i + 1);
			send(ii);
		}
		vi cc = wait();
		int b = 0;
		for (int l = 0; l < L; l++)
			if (cc[l])
				b |= 1 << l;
		for (int i = 0; i < N; i++)
			for (int j = i; j < N; j++)
				if ((bb[i] | bb[j]) == b)
					return { i + 1, j + 1 };
		return { -1, -1 };
	}
}

Compilation message (stderr)

avoid.cpp: In function 'int count(int)':
avoid.cpp:13:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  return b == 0 ? 0 : count(b & b - 1) + 1;
      |                                ~~^~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 65.000025 / 75