Submission #1051018

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

avoid

#include "avoid.h"
#include <cassert>
#include <vector>
//#include <iostream>
 
using namespace std;
 
const int N = 1000, LN = 10, L = 26;
 
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
		vi bb(N), ij(1 << L, -1);
		for (int j = 0, b = 0; j < N; j++) {
			bool good = false;
			while (b < 1 << L) {
				bb[j] = b++;
				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;
					}
				if (good) {
					for (int i = 0; i <= j; i++)
						ij[bb[i] | bb[j]] = i * N + j;
					break;
				}
			}
			if (!good)
				return { -1, -1 };
		}
		cerr << "{ ";
		for (int j = 0; j < N; j++)
			cerr << bb[j] << ", ";
		cerr << "}";
		return { -1, -1 };
#endif
		int bb[N] = { 255, 383, 639, 927, 1151, 2175, 3231, 3879, 4223, 5407, 5799, 6571, 6735, 8081, 8319, 9615, 9775, 10551, 10951, 16511, 18311, 20663, 21319, 23833, 27049, 27675, 28384, 29393, 30467, 32895, 35719, 38283, 40007, 41167, 41827, 42643, 44361, 47260, 49455, 50333, 51798, 54833, 63780, 65663, 68999, 70539, 73265, 75555, 76752, 77911, 79074, 81162, 82355, 82523, 84645, 87496, 98973, 99637, 104801, 109736, 111141, 115649, 118281, 123971, 131199, 134791, 136995, 140185, 142800, 143511, 145096, 145964, 148141, 148813, 150372, 153686, 156849, 164307, 165466, 170776, 171232, 174123, 177204, 183570, 185729, 197790, 198987, 214640, 217400, 221958, 223428, 233638, 238000, 245845, 262271, 268935, 272259, 273193, 273609, 274703, 276049, 279645, 280855, 283034, 294208, 296730, 297173, 298402, 307601, 311947, 316256, 318476, 328519, 329388, 331540, 333882, 349702, 350432, 352361, 365256, 370758, 378002, 394724, 395805, 400425, 402462, 416321, 418402, 422784, 430157, 437824, 442772, 461010, 471562, 472352, 485640, 492324, 494609, 524415, 531207, 531625, 536083, 536971, 537148, 538560, 542251, 543681, 549094, 550193, 555022, 561365, 562964, 567720, 574233, 575666, 591756, 592078, 604681, 609302, 623826, 641376, 643128, 651522, 658531, 660146, 665925, 672135, 685600, 696843, 713860, 721461, 725472, 726104, 744000, 756993, 786873, 795286, 804546, 820263, 825418, 829216, 844356, 854914, 856676, 872836, 893104, 935216, 952460, 992259, 1001506, 1048703, 1060611, 1061645, 1061939, 1062337, 1067063, 1068233, 1069986, 1073493, 1079880, 1080452, 1083344, 1084942, 1085749, 1092272, 1098188, 1104080, 1106469, 1116949, 1117283, 1119912, 1122966, 1132312, 1134667, 1152832, 1155384, 1173761, 1180462, 1182154, 1189460, 1217185, 1220762, 1227072, 1229894, 1241122, 1251716, 1253478, 1259537, 1278540, 1294473, 1311399, 1312120, 1318026, 1335480, 1337634, 1344707, 1348118, 1402116, 1418753, 1447188, 1452144, 1476904, 1523971, 1574372, 1579416, 1594885, 1610794, 1614658, 1625348, 1647641, 1648804, 1659216, 1683585, 1722456, 1753665, 1757448, 1770792, 1802626, 1835849, 1838108, 1849377, 1864208, 1884258, 1969281, 2035777, 2097279, 2109313, 2110745, 2111563, 2115727, 2117026, 2117187, 2118757, 2120496, 2122270, 2132247, 2133224, 2134611, 2135689, 2138538, 2155204, 2164247, 2167079, 2168644, 2171109, 2175628, 2183321, 2187593, 2213976, 2220802, 2224224, 2231180, 2232801, 2238274, 2259073, 2277670, 2294435, 2296884, 2311616, 2328088, 2332675, 2360248, 2371108, 2384276, 2396338, 2398536, 2410024, 2426224, 2443793, 2466828, 2490702, 2493578, 2531528, 2548240, 2560133, 2622667, 2624212, 2658630, 2660752, 2668580, 2675272, 2689299, 2704224, 2712656, 2737281, 2760914, 2788992, 2793761, 2830608, 2838538, 2890758, 2898448, 2902312, 3015209, 3080896, 3151004, 3156172, 3171888, 3179210, 3200003, 3245322, 3248262, 3278087, 3293211, 3297604, 3319813, 3413600, 3416597, 3424908, 3473828, 3475540, 3673377, 3738122, 3751980, 3811872, 3818128, 3833884, 3948929, 4038720, 4194431, 4207491, 4208918, 4209832, 4214534, 4215962, 4219704, 4230818, 4231881, 4236317, 4236740, 4245779, 4247668, 4254340, 4262446, 4265300, 4266164, 4268520, 4269714, 4283395, 4288585, 4301580, 4327603, 4328717, 4333121, 4346418, 4348104, 4359953, 4383042, 4394632, 4400165, 4415873, 4441220, 4448784, 4458968, 4461164, 4464821, 4470050, 4475429, 4494418, 4510880, 4515850, 4526857, 4532832, 4555184, 4591921, 4654466, 4719459, 4738193, 4739912, 4752654, 4753513, 4764177, 4808852, 4819524, 4852372, 4853862, 4860296, 4954120, 4982345, 4994180, 5003778, 5046413, 5114898, 5128261, 5244443, 5259973, 5275821, 5287200, 5308711, 5326930, 5337632, 5378258, 5400192, 5508484, 5511249, 5530633, 5585024, 5603432, 5669442, 5772930, 5775476, 5806086, 5816720, 5867024, 5903136, 6046220, 6292209, 6297989, 6299400, 6308268, 6334672, 6360258, 6389775, 6428728, 6430826, 6450432, 6465028, 6504545, 6562067, 6571297, 6606872, 6686211, 6833682, 6885425, 6893056, 6947916, 7102500, 7111552, 7155714, 7344976, 7355394, 7375369, 7408016, 7439008, 7492640, 7545096, 7602315, 7717888, 7995713, 8388735, 8403331, 8404005, 8404800, 8410762, 8411292, 8414100, 8417337, 8425240, 8426254, 8434344, 8439078, 8440257, 8447184, 8457922, 8458837, 8462698, 8464564, 8471309, 8472678, 8475760, 8493190, 8509984, 8524059, 8529159, 8539665, 8553137, 8561473, 8577128, 8578562, 8585697, 8592456, 8623632, 8651934, 8653792, 8663266, 8668707, 8677968, 8684115, 8727564, 8736001, 8749323, 8802468, 8816678, 8833160, 8848024, 8855601, 8913830, 8918093, 8923848, 8934674, 8959072, 8964613, 8995017, 9013274, 9045232, 9048900, 9064483, 9077140, 9184704, 9191694, 9201824, 9212289, 9252870, 9320512, 9404484, 9439026, 9439533, 9441746, 9479190, 9503956, 9522186, 9537888, 9570898, 9573513, 9595648, 9604129, 9720449, 9736516, 9767472, 9839234, 9855044, 9996419, 10031202, 10034688, 10100755, 10228234, 10289425, 10487461, 10489169, 10508033, 10511684, 10534016, 10539424, 10560041, 10633784, 10650693, 10692896, 10699788, 10754073, 10826496, 10900496, 11013260, 11059219, 11116808, 11240480, 11538996, 11542574, 11550960, 11609728, 11666248, 11797578, 11837697, 12063016, 12081216, 12584393, 12585625, 12593251, 12624436, 12644616, 12669089, 12682114, 12722342, 12743744, 12769284, 12779578, 12884001, 13009027, 13109532, 13115824, 13124675, 13190688, 13312768, 13402156, 13640837, 13779360, 13831184, 13929536, 13975558, 14024792, 14549505, 14701062, 14717201, 14730336, 14813570, 14950984, 15007844, 15222856, 15466704, 15798785, 16252978, 16777343, 16792195, 16797576, 16800148, 16803234, 16803409, 16815010, 16816728, 16820100, 16822295, 16829636, 16834842, 16847003, 16850113, 16851534, 16860430, 16869474, 16876008, 16896580, 16912911, 16914601, 16919621, 16920936, 16929820, 16941921, 16976422, 16983314, 16997888, 17018945, 17040998, 17042737, 17050008, 17059915, 17080486, 17085536, 17090828, 17117236, 17122072, 17140353, 17171128, 17172233, 17195141, 17217792, 17285168, 17302844, 17305296, 17319144, 17322672, 17328673, 17336587, 17346760, 17357856, 17375441, 17377668, 17442314, 17465542, 17568916, 17579520, 17596947, 17633545, 17655040, 17702961, 17826277, 17828438, 17854658, 17863844, 17868841, 17893554, 17896198, 17940501, 17982473, 18006658, 18056336, 18099280, 18109457, 18219404, 18221760, 18356293, 18357506, 18400336, 18481520, 18630659, 18776224, 18875250, 18879890, 18883635, 18903308, 18908485, 18943528, 18981379, 19005597, 19024096, 19050640, 19155014, 19202252, 19272770, 19407652, 19465229, 19480710, 19501600, 19534401, 19681360, 19702912, 19926054, 19965448, 19997762, 20010240, 20023680, 20087344, 20202304, 20259073, 20383752, 20449425, 20974388, 20975943, 20977264, 20981902, 21022048, 21054338, 21080136, 21132032, 21185553, 21299538, 21333002, 21397548, 21432388, 21498917, 21520460, 21562914, 21639298, 21764192, 21889300, 22028844, 22039200, 22053204, 22089756, 22154336, 22319233, 22339616, 22691969, 23070341, 23105610, 23152688, 23335080, 23365649, 23614472, 23633954, 24658178, 24904708, 25169066, 25182407, 25208112, 25240337, 25256640, 25267203, 25299841, 25333844, 25499688, 25550850, 25575521, 25581570, 25691670, 25722933, 25954596, 26088456, 26215128, 26235160, 26249616, 26353956, 26419336, 26509410, 26742918, 26821122, 27036160, 27269700, 27303964, 27314185, 27463716, 27533698, 27918412, 27942913, 28329089, 28381328, 28844560, 28999682, 29374992, 29385864, 29491731, 29605896, 29641088, 29688325, 29888801, 30410946, 30545152, 30683200, 31064104, 31983360, 33554559, 33569539, 33576833, 33577485, 33578160, 33582416, 33583388, 33593764, 33596312, 33599042, 33600864, 33608400, 33625115, 33630231, 33633832, 33638082, 33648836, 33653526, 33671299, 33687460, 33694286, 33699977, 33704971, 33722698, 33734834, 33743400, 33754464, 33793154, 33819687, 33821492, 33824448, 33830036, 33834216, 33842698, 33859858, 33865799, 33868321, 33882509, 33891440, 33902627, 33964803, 34045993, 34081129, 34086424, 34087762, 34100293, 34114241, 34153122, 34183684, 34212241, 34234506, 34242680, 34345043, 34350401, 34367524, 34476184, 34571328, 34605738, 34607310, 34614316, 34639137, 34648102, 34679364, 34702405, 34703752, 34735257, 34750944, 34780672, 34803762, 34817156, 34878082, 34898190, 34931288, 34950160, 34955393, 35002912, 35135637, 35209768, 35265600, 35410952, 35459360, 35654425, 35656586, 35664453, 35686000, 35719844, 35751057, 35777536, 35783766, 35807267, 35862592, 35916240, 35975296, 36077953, 36128772, 36181154, 36241948, 36242698, 36323649, 36343940, 36446221, 36471432, 36524544, 36536354, 36717841, 36722818, 36971588, 37126162, 37249090, 37277952, 37486768, 37754979, 37765429, 37781899, 37850152, 37865792, 37882642, 37889248, 37926928, 37949840, 38021254, 38110724, 38150169, 38176836, 38282785, 38338916, 38357040, 38404615, 38576200, 38798659, 38802980, 38825994, 38846760, 38979586, 39347456, 39453744, 39847081, 39864468, 40142088, 40407058, 40935448, 41025924, 41026120, 41420803, 41943703, 41951692, 42014764, 42034200, 42049809, 42162178, 42207544, 42242584, 42348804, 42475563, 42484176, 42487044, 42608660, 42664204, 43025120, 43026513, 43143684, 43302921, 43320578, 43517584, 44049938, 44075160, 44105960, 44139296, 44205314, 44319268, 44761217, 45221928, 45654048 };
		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 };
		assert(false);
		return { -1, -1 };
	}
}

Compilation message (stderr)

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

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