Submission #1099989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099989		marvinthang	How to Avoid Disqualification in 75 Easy Steps (CEOI23_avoid)	C++17	100 / 100	2 ms	608 KiB

avoid

/*************************************
*    author: marvinthang             *
*    created: 25.08.2023 11:00:17    *
*************************************/

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

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const int N = 1000;
const int LOG2 = 10;
const int NUM_ROBOT = 26;
vector <long long> plan = {10228358, 255, 1823, 2919, 3499, 3795, 5037, 5491, 6493, 7062, 9139, 9581, 10813, 11209, 11669, 13455, 16033, 17358, 17912, 19130, 21110, 22059, 22727, 26309, 27762, 28955, 31116, 33749, 34278, 35290, 36457, 37467, 38967, 42819, 45285, 45358, 48153, 50579, 52302, 53705, 54332, 61064, 67182, 67902, 70364, 72870, 75444, 77945, 79298, 79621, 82263, 83102, 84629, 88673, 89416, 92323, 99501, 102154, 104554, 107364, 111250, 121604, 122895, 132725, 134797, 135907, 137848, 138315, 139708, 140890, 148329, 148901, 149972, 153898, 155703, 159520, 161873, 166706, 169304, 174250, 179072, 185105, 187584, 193542, 197616, 202921, 205191, 209939, 210958, 221740, 229582, 232005, 241985, 246360, 263847, 264689, 267853, 268088, 270935, 276523, 278845, 281894, 282842, 291985, 295658, 297628, 302402, 304329, 311651, 312916, 321810, 324099, 330515, 332642, 339014, 346189, 349828, 360603, 369713, 376320, 379296, 386368, 394700, 396311, 406154, 406817, 418020, 430916, 445488, 450712, 475909, 479282, 509057, 526009, 529644, 531274, 531905, 532854, 536071, 541277, 541620, 547862, 549315, 559779, 566828, 567593, 569748, 576645, 578186, 579936, 583764, 591987, 594229, 595211, 600217, 615010, 623701, 639529, 652320, 656626, 665480, 673931, 686116, 688189, 694540, 697168, 722566, 724260, 738377, 741712, 758338, 787862, 792760, 799138, 806664, 811782, 854722, 860218, 885125, 907280, 919660, 955905, 987912, 991904, 1051230, 1053877, 1054534, 1056044, 1057642, 1061560, 1066315, 1067315, 1070800, 1077356, 1082780, 1088193, 1091761, 1093718, 1098540, 1106122, 1116066, 1121816, 1125387, 1128656, 1135370, 1139140, 1147175, 1152273, 1174018, 1182147, 1184922, 1188561, 1215840, 1216527, 1246761, 1253958, 1262866, 1280388, 1294433, 1311542, 1321285, 1322012, 1329302, 1330273, 1337089, 1343609, 1378760, 1380398, 1396897, 1442648, 1460802, 1479042, 1484292, 1524368, 1546272, 1575701, 1582371, 1593893, 1598552, 1607218, 1616134, 1638761, 1657504, 1689612, 1717024, 1724561, 1739400, 1810450, 1845322, 1872992, 1901699, 1933520, 1966611, 1974309, 2035777, 2100444, 2103784, 2106014, 2110292, 2112290, 2114663, 2116171, 2118066, 2124088, 2127384, 2130319, 2131253, 2135249, 2138701, 2146981, 2164193, 2166384, 2167319, 2182530, 2188564, 2191493, 2200480, 2203762, 2217987, 2231850, 2233734, 2238565, 2240618, 2245404, 2263189, 2303553, 2306328, 2333712, 2367360, 2368866, 2381908, 2382888, 2384204, 2398342, 2427433, 2449968, 2466826, 2490707, 2491300, 2499732, 2517002, 2544160, 2591234, 2623942, 2624793, 2647264, 2655322, 2671940, 2682889, 2698252, 2705025, 2728067, 2753291, 2759236, 2802182, 2885925, 2918450, 2954384, 3047521, 3094528, 3156140, 3161154, 3181112, 3195344, 3211421, 3213962, 3281189, 3287090, 3294252, 3343444, 3387904, 3421344, 3441938, 3465236, 3477769, 3539114, 3556736, 3675192, 3690578, 3697168, 3735954, 3741186, 3825924, 3883042, 3944451, 4030984, 4197605, 4201735, 4203244, 4203579, 4204883, 4208209, 4212530, 4216985, 4221454, 4223202, 4231920, 4236822, 4243804, 4246305, 4260330, 4266792, 4277443, 4279817, 4295828, 4301386, 4313137, 4330440, 4340872, 4346501, 4351376, 4358795, 4367472, 4391093, 4395110, 4398656, 4433156, 4460777, 4465433, 4475778, 4493341, 4494978, 4503648, 4523278, 4528180, 4579364, 4589766, 4603979, 4628865, 4655256, 4698114, 4720592, 4720719, 4731442, 4739852, 4746305, 4755555, 4806016, 4826136, 4850734, 4882834, 4884704, 4917521, 4985603, 4991122, 4991524, 5062760, 5113184, 5246136, 5254914, 5267749, 5281216, 5282310, 5320844, 5325393, 5333018, 5374614, 5380165, 5424131, 5520000, 5538216, 5558544, 5572162, 5638409, 5771562, 5785641, 5800517, 5850148, 5906457, 6029428, 6292662, 6327363, 6336816, 6349352, 6357830, 6424920, 6489636, 6508616, 6562904, 6586476, 6603018, 6620040, 6622496, 6819929, 6839808, 6897925, 6948424, 7061632, 7110932, 7340707, 7362817, 7377929, 7381073, 7606880, 7749680, 7873156, 8257728, 8392497, 8394442, 8395892, 8399182, 8409262, 8411724, 8413369, 8418081, 8426268, 8431736, 8434850, 8444576, 8448261, 8454885, 8460740, 8463672, 8483905, 8489241, 8504835, 8521945, 8525604, 8529091, 8553797, 8566817, 8571202, 8586121, 8591506, 8602786, 8655119, 8664146, 8667675, 8669972, 8675792, 8696200, 8705033, 8719397, 8730696, 8766048, 8786352, 8790577, 8871942, 8915628, 8938548, 8951616, 8982088, 8995602, 9019588, 9048147, 9060684, 9069059, 9120260, 9143680, 9184912, 9208513, 9235456, 9240920, 9309194, 9440482, 9447447, 9467152, 9470644, 9471502, 9521537, 9556496, 9573185, 9585313, 9629824, 9642252, 9723392, 9723946, 9732198, 9766000, 9841024, 9929736, 9964144, 9969805, 10010680, 10110084, 10258435, 10497668, 10502865, 10519595, 10568040, 10577929, 10621453, 10642504, 10658448, 10683665, 10749317, 10766488, 10819842, 10915912, 11010403, 11047024, 11075662, 11149476, 11273796, 11292684, 11537296, 11540522, 11574528, 11641090, 11699360, 11714570, 11945988, 12320789, 12596100, 12615742, 12621955, 12656679, 12664948, 12714759, 12772864, 12846252, 12855873, 12951824, 12988484, 12998912, 13107633, 13112453, 13118498, 13148328, 13156546, 13386769, 13447200, 13525120, 13656392, 13701536, 13767692, 13959193, 14174228, 14352450, 14691592, 14733330, 14750788, 14778505, 14958627, 15139392, 15222944, 15731730, 15934464, 16285960, 16781132, 16783235, 16788134, 16790806, 16795308, 16796441, 16798101, 16804674, 16814251, 16819920, 16824396, 16827953, 16835849, 16847973, 16853416, 16862384, 16871466, 16877084, 16885893, 16892210, 16914518, 16922152, 16930624, 16934925, 16949602, 16975139, 17007266, 17041799, 17044432, 17072655, 17075288, 17083680, 17125897, 17154244, 17170680, 17183252, 17203477, 17239556, 17304678, 17308212, 17314584, 17330817, 17347649, 17367258, 17376836, 17434821, 17443888, 17450514, 17469729, 17481840, 17502221, 17580195, 17598210, 17602570, 17630600, 17633302, 17713410, 17828276, 17838606, 17850786, 17898050, 17916049, 17958225, 17976580, 17996802, 18113096, 18141224, 18220226, 18356249, 18383948, 18468992, 18481888, 18505864, 18647172, 18886851, 18902033, 18925960, 18973457, 18989129, 19006746, 19021974, 19071047, 19136574, 19166272, 19273761, 19365900, 19399557, 19440674, 19468578, 19470416, 19533440, 19923569, 19933569, 19957767, 20013092, 20199432, 20201539, 20252192, 20484368, 20521032, 20726788, 20994340, 20996784, 21037339, 21088336, 21110931, 21138441, 21139596, 21234593, 21238314, 21259276, 21312256, 21446944, 21528725, 21686272, 21825601, 21921864, 22020809, 22029319, 22053220, 22072448, 22119056, 22123524, 22224936, 22545282, 22814992, 22839330, 23071253, 23078180, 23173632, 23210242, 23273664, 23351426, 23412756, 23594033, 24709248, 25184466, 25202194, 25224258, 25236628, 25299467, 25316376, 25346436, 25362489, 25428629, 25497889, 25690894, 25695528, 25778180, 25960740, 25970760, 26087616, 26226785, 26231124, 26297354, 26349834, 26517552, 26577152, 27271284, 27304458, 27330722, 27350528, 27525401, 27812608, 27820101, 27953160, 28083328, 28246032, 28443154, 28901633, 29361546, 29413448, 29493796, 29639776, 29690370, 29885955, 29929984, 30475584, 30572624, 31461936, 31471744, 32505884, 33561316, 33564550, 33565154, 33568584, 33572911, 33577377, 33579228, 33585673, 33590541, 33592752, 33594115, 33608802, 33611954, 33620409, 33621705, 33629521, 33634864, 33654870, 33657164, 33699988, 33705492, 33719508, 33727013, 33729539, 33735362, 33753355, 33771672, 33817972, 33821723, 33826354, 33880192, 33891341, 33898794, 33947821, 33950401, 33956166, 34083441, 34096326, 34114124, 34129176, 34140676, 34146853, 34193572, 34193667, 34210071, 34223200, 34341772, 34342113, 34365489, 34417680, 34441984, 34494976, 34521122, 34607645, 34611851, 34622800, 34630785, 34672711, 34710176, 34734650, 34741792, 34775116, 34810176, 34903046, 34933344, 34939156, 35133640, 35136052, 35170369, 35194385, 35205130, 35275017, 35524868, 35673409, 35674630, 35697700, 35717227, 35783827, 35818244, 35849356, 35905538, 35916814, 35918274, 36012564, 36054056, 36176594, 36217601, 36309392, 36343826, 36703009, 36718212, 36785184, 36881424, 36995296, 37095441, 37560448, 37760044, 37770050, 37781721, 37819560, 37851522, 37869056, 37896222, 37897768, 37946898, 38015633, 38109473, 38275428, 38354994, 38374464, 38537738, 38572168, 38682704, 38846852, 38864272, 38953120, 38963236, 39060553, 39076376, 39328770, 39522816, 39852081, 39871044, 39882000, 39977793, 40050705, 40192064, 40243488, 40378403, 40386712, 40894734, 41953874, 41992841, 42011715, 42035332, 42047524, 42111272, 42140174, 42207136, 42239249, 42246724, 42436624, 42479809, 42607640, 42996066, 43030546, 43057302, 43123974, 43525280, 43533120, 44042269, 44048808, 44175498, 44421120, 44574792, 44597784, 44639234, 44697603, 45351240, 45355521, 46140616, 46161939, 46167044, 46276873, 46481420, 46825477, 47196256, 47253000, 47319808, 47456386, 48247298, 48398432, 50334873, 50348396, 50348615, 50374682, 50402180, 50469256, 50630977, 50667617, 50681858, 50864681, 50890928, 51068948, 51257474, 51414275, 51446356, 51455490, 51774488, 51789857, 52168000, 52446000, 52454410, 52482208, 52527552, 52609544, 52888640, 53477580, 54599941, 54791236, 54923273, 55050850, 55054612, 55075200, 55619616, 56660036, 56888064, 58742801, 58856096, 58983446, 59056264, 59310721, 59769002, 59810056, 59867141, 60819808, 61346368, 62005252, 63980160};

pair <int, int> scout(int R, int H) {
    if (R == 10 && H == 1) {
        REP(bit, LOG2) {
            vector <int> p;
            FORE(i, 1, N) if (BIT(i, bit)) p.push_back(i);
            send(p);
        }
        vector <int> v = wait();
        int res = 0;
        REP(i, LOG2) if (v[i]) res ^= MASK(i);
        return pair {res, res};
    }
    if (R == 20 && H == 20) {
        int l = 1, r = N - 1;
        while (l <= r) {
            int m = l + r >> 1;
            vector <int> p;
            FORE(i, l, m) p.push_back(i);
            send(p);
            p = wait();
            if (p[0]) r = m - 1;
            else l = m + 1;
        }
        int res1 = l;
        l = 1, r = N;
        while (l <= r) {
            int m = l + r >> 1;
            vector <int> p;
            FORE(i, l, m) if (i != res1) p.push_back(i);
            send(p);
            p = wait();
            if (p[0]) r = m - 1;
            else l = m + 1;
        }
        if (l > N) l = res1;
        return pair {res1, l};
    }
    REP(i, NUM_ROBOT) {
        vector <int> pos;
        REP(j, N) if (BIT(plan[j], i)) pos.push_back(j + 1);
        send(pos);
    }
    vector <int> t = wait();
    int mask = 0;
    REP(i, NUM_ROBOT) if (t[i]) mask ^= MASK(i);
    REP(i, N) REP(j, N) if ((plan[i] | plan[j]) == mask) return pair{i + 1, j + 1};
    return pair{-1, -1};
}

Compilation message (stderr)

avoid.cpp: In function 'std::pair<int, int> scout(int, int)':
avoid.cpp:66:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |             int m = l + r >> 1;
      |                     ~~^~~
avoid.cpp:77:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |             int m = l + r >> 1;
      |                     ~~^~~

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