oj.uz

Submission #1056804

# Submission time Handle Problem Language Result Execution time Memory
1056804 2024-08-13T11:24:09 Z YassineBenYounes How to Avoid Disqualification in 75 Easy Steps (CEOI23_avoid) C++17
85 / 100
 201 ms 31840 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
////////////////////Only Clear Code//////////////////////////
 
void usaco_problem(){
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
}
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const int mx = 1e6+5;
const int LOG = 22;
const int inf = 1e9;
const ll mod = 1e9+7;
const int sq = 300;
const int n = 1000;
const int plan[1005] = {53479530, 2163433, 1811520, 8983008, 13895204, 153898, 10059922, 1663004, 4986180, 5793344, 8434068, 33655107, 35671081, 4857885, 8463244, 17978528, 934426, 104554, 43335824, 17170535, 39985290, 4277921, 139708, 4292956, 509057, 33624143, 34687522, 202921, 621600, 44053064, 1589453, 36457, 5771666, 8430746, 33690394, 36308490, 10113408, 6439648, 6521616, 4557321, 33625793, 35134082, 16975142, 16925394, 82263, 27922500, 561310, 13263364, 161873, 1054534, 33581890, 7537712, 17465560, 53018693, 6564898, 17342016, 39977169, 34677267, 132725, 17048857, 8706116, 17830059, 42229833, 19620096, 5295392, 30507056, 15221028, 3953672, 37763680, 339014, 23675394, 1321186, 3214481, 8851463, 16860753, 551500, 42372224, 2918952, 369713, 2968080, 59809873, 25694223, 54677764, 3223692, 10486486, 18428288, 29474819, 9278720, 13115856, 4981644, 70364, 17894180, 21038227, 34641248, 6685258, 43260672, 159520, 33855761, 47317268, 4588210, 33592853, 34013379, 8208416, 16867660, 18352412, 19275804, 2245709, 36176659, 4870193, 6367780, 16795308, 4419652, 19203408, 8693508, 19571720, 2625897, 3260948, 9052776, 41972996, 21168308, 19464358, 50365772, 16886789, 581721, 16844891, 17110083, 6428756, 59772956, 7407629, 17219880, 241985, 31596808, 1163564, 1200206, 16888992, 67182, 9452037, 330515, 18210817, 17269408, 9736218, 22806689, 21364878, 641728, 26935816, 11019013, 7864403, 38560004, 4546819, 111250, 17899574, 42238038, 2919, 8396388, 3940930, 12879370, 4470836, 12894536, 1542336, 379296, 5183552, 34604466, 4600912, 1222149, 1904848, 21241472, 21536908, 2754898, 2228798, 1115335, 625187, 1616656, 10520966, 7398528, 42467534, 610350, 36741282, 263847, 8454955, 860302, 23467009, 33819850, 8536963, 88673, 33886598, 4494500, 11543636, 35995667, 2130235, 8511768, 42123285, 22059, 137848, 563568, 193542, 1441965, 276523, 26309, 6865296, 4203579, 10880081, 2384421, 321810, 2263189, 10531843, 8724509, 34133256, 923520, 2140753, 34114693, 179072, 8798486, 1073933, 2640996, 18878008, 5037, 33567192, 1614276, 4735143, 34409988, 4270234, 33776673, 36390916, 267853, 25175244, 27334016, 25311280, 37890433, 37245008, 1360688, 54332, 1036800, 27296866, 1966186, 37235714, 2106595, 8655507, 18384945, 5016194, 37912936, 9461910, 34801802, 18252035, 4236828, 5587648, 19008067, 11567224, 8857696, 1051230, 4213529, 18164032, 12626210, 11665802, 35011584, 10555730, 2151045, 17597124, 1710612, 396311, 4457081, 592981, 19187201, 8497712, 34185506, 4460830, 45232129, 16909722, 246360, 42083378, 17793042, 4223456, 50340487, 9701992, 102154, 34899465, 797752, 2102938, 155703, 17912, 8747009, 75444, 17302859, 39125003, 582820, 45358, 8455513, 4233640, 36340128, 4285001, 4765714, 51971201, 59312138, 1056044, 37847697, 28955, 2120112, 232005, 51446342, 149972, 938068, 34603629, 532854, 72870, 10623624, 42993089, 43062282, 18915367, 16797460, 724552, 40901633, 5491, 122895, 8414776, 42305056, 4201735, 20976457, 430916, 9575744, 34345101, 9110037, 33622644, 10536460, 8394658, 50897161, 135907, 9610504, 39878734, 1270656, 18929984, 56635521, 1053877, 44565036, 1070800, 50622469, 5836825, 5769318, 42242316, 1294355, 669890, 34906168, 1153553, 39006336, 4216877, 1573857, 58985510, 39469128, 4228901, 255, 35666116, 8996361, 33588028, 12650068, 5375904, 2107471, 4096129, 27402786, 3027104, 34091301, 3409669, 12853362, 332642, 4203244, 26877972, 2305538, 17056178, 58851512, 2541577, 24135752, 84629, 2730128, 197616, 8657422, 41978576, 8422031, 1067339, 689926, 2196788, 1247345, 29885152, 21811216, 1246028, 43172128, 8457668, 35927312, 9438315, 9212481, 6434914, 3150449, 83102, 24186368, 229582, 1706373, 569954, 3236129, 21692768, 2428988, 4338309, 51091456, 6627976, 22021304, 67902, 50446358, 2834499, 2393103, 33572708, 8522660, 140890, 35193944, 2689606, 16784025, 17838668, 20021509, 16255168, 23107594, 6887808, 22057236, 9552449, 51003952, 34088987, 20186185, 19012626, 526009, 13631885, 35719960, 6882380, 37948482, 34163856, 16812429, 19468376, 21384256, 40899332, 3346626, 44730432, 1872902, 2295177, 27287704, 295658, 9515281, 537297, 2674978, 166706, 8931654, 7143745, 16829314, 2239768, 1118503, 46418208, 33784857, 17506449, 33598994, 52454080, 7477536, 9176468, 8597800, 60821523, 25432458, 9995912, 5387024, 17310362, 13992072, 944448, 278845, 5313093, 210958, 43534353, 15737384, 26501504, 61999232, 58723905, 14686481, 10100803, 12734626, 3448854, 39848497, 656626, 19106056, 4792515, 37093552, 264689, 9459810, 2495124, 23478788, 4367808, 2770193, 1583320, 13670976, 11209, 5423244, 5476385, 8401223, 3703905, 8399224, 34084402, 9644161, 543027, 34381970, 1084070, 1320588, 9175273, 2166113, 33835527, 41961360, 26299400, 89416, 46205059, 16994584, 38019402, 12361984, 26394690, 47579650, 33605745, 51396880, 10581056, 5286021, 18908008, 1788929, 268088, 209939, 531274, 56103456, 3795, 31116, 16804020, 221740, 33575331, 723602, 17137934, 2640011, 2558276, 1082780, 19531813, 35689612, 38183937, 9970821, 10093094, 627723, 99501, 866576, 270935, 45285, 2386442, 23333264, 2631052, 8733352, 11278360, 5689600, 1061560, 7062, 4358923, 1215570, 2240781, 57155618, 12124930, 79298, 36717768, 418020, 169304, 5391457, 6353160, 16876085, 282842, 22545930, 42049673, 52438788, 2011152, 38668322, 2716161, 5289025, 25395520, 311651, 25252033, 1180315, 25270352, 15011972, 16957637, 19153520, 12746835, 4199641, 18374880, 8450752, 4722480, 38310412, 4924944, 4204883, 6820906, 33561686, 6705288, 38470661, 2166935, 6407426, 17046098, 12724235, 37896222, 2363208, 11669, 3825670, 475909, 35989633, 6588498, 34099908, 8662672, 51427336, 54601793, 4243670, 34234466, 324099, 2279042, 2917552, 6294468, 17630236, 148901, 15803393, 34756613, 10698898, 205191, 35801138, 4297254, 16929287, 50579, 2433236, 531905, 10897600, 13109786, 17876800, 8919189, 820561, 4868488, 33651208, 757936, 8604930, 17476097, 10781219, 34743492, 1159252, 1640324, 3313671, 16783844, 18958350, 17322374, 26478723, 33957976, 12717456, 138315, 3424302, 34278, 33892620, 46399751, 2470176, 46826504, 1379369, 1068593, 6308028, 17697924, 11111428, 11602084, 3428625, 35185154, 33808514, 33580425, 479282, 53559809, 4410884, 54870040, 9581, 29397521, 9139, 1316227, 51478569, 187584, 19474048, 5801225, 4265872, 27790088, 7406106, 13336705, 2220136, 2136800, 346189, 17371442, 304329, 33755413, 8579105, 536071, 574023, 16815630, 36012612, 33948020, 4622433, 59671040, 2757412, 52830273, 11346946, 6305297, 38967, 12586764, 37467, 38338838, 25486338, 7241734, 25563472, 26247969, 11878409, 16951618, 1403920, 48268336, 8814993, 1057642, 8967298, 17358, 34771522, 2462912, 33749, 37839152, 281894, 550786, 6816372, 54550628, 4302120, 44130338, 8423651, 9464480, 21110, 960524, 14721345, 5277756, 37225796, 4329930, 16922152, 25580064, 21138444, 48759361, 41681048, 360603, 42665728, 445488, 56295440, 62948736, 2112290, 4252422, 60850442, 35709220, 1475876, 18040976, 44433445, 4262818, 1098922, 1590610, 79621, 4351124, 16838960, 2315524, 2115378, 8783554, 1311698, 61064, 4314129, 795480, 16033, 5265926, 1636356, 5005858, 33654968, 25822369, 529644, 65536144, 17117336, 2444418, 174250, 1639722, 12604520, 1444641, 18401290, 52302, 1139786, 1134824, 52593684, 406154, 926731, 2151506, 16802403, 17461257, 27527685, 16818298, 4656152, 10491657, 50860148, 1124784, 42889216, 9976072, 8946804, 28639300, 2252289, 8443169, 16984708, 33565094, 1218712, 1333385, 21013154, 3965004, 6327427, 26026017, 394700, 11026455, 1323337, 50596800, 22169634, 8407257, 4479297, 1121928, 37620224, 134797, 13455, 8408710, 590237, 9257072, 37766794, 8440116, 788694, 3166882, 11468812, 185105, 4834400, 107364, 49284736, 4197605, 312916, 2185241, 22727, 4351242, 53705, 386368, 33883429, 5532161, 46668804, 16798821, 21177089, 16846056, 20999171, 7618946, 37867530, 2332192, 10813, 9699686, 17417473, 38806808, 35258665, 19130, 3195206, 34867397, 44040547, 1753640, 36864529, 4391034, 2122194, 1340512, 5095436, 11799824, 20578834, 29648912, 50791944, 18089172, 17051394, 34226825, 8815148, 19958976, 28315685, 14262784, 729866, 1148466, 14176776, 17189137, 4860961, 541620, 1909284, 13042848, 16790806, 18093585, 26853380, 50488400, 58786160, 8940609, 9134240, 55607940, 33951790, 4522214, 50875680, 6856753, 36896806, 18490656, 19147044, 53217538, 46219301, 53485716, 21336321, 450712, 148329, 35934732, 349828, 2703672, 62923584, 17993828, 11420416, 52777024, 1823, 48153, 92323, 291985, 688461, 2789960, 5583876, 8523837, 8561236, 8606528, 17122346, 17317000, 19173513, 19400213, 21250374, 25303174, 31458330, 33691048, 35459360, 36247648, 36487425, 38312128, 42795586, 49479744, 50332913, 54798472, 11587720, 40112576, 3317833, 10773664, 58792193, 46239764, 34881960, 34431168, 9637392, 20189234, 34349617, 33736868, 5505365, 19923843, 8413294, 33595947, 3159306, 2901510, 2720641, 52531968, 4752978, 52506672, 23081004, 21498058, 17883672, 3156019, 2359751, 38798375, 2110292, 1206298, 62966272, 48514056, 2269424, 8590476, 36222977, 2145540, 2100444, 30740482, 1902599, 1190662, 1091937, 793125, 694531, 599457, 376320, 302402, 3499, 6493, 27762, 35290, 42819, 547866, 674017, 806657, 8926249, 12670994, 14430336, 14778952, 21055240, 21497132, 21571624, 24641792, 26085416, 29907008, 31514628, 35013890, 39487744, 43005472, 50769922, 52723872, 59787332};


#include "avoid.h"

vi robot[30];

std::pair<int, int> scout(int R, int H){
    map<int, pii> mp;
    for(int i = 1; i <= n;i++){
        for(int j = i;j <= n;j++){
            int x = plan[i-1] | plan[j-1];
            mp[x] = {i, j};
        }
    }
    for(int i = 0; i < 1000;i++){
        int x = plan[i];
        for(int j = 0;j < 26;j++){
            if(x & (1 << j)){
                robot[j].pb(i+1);
            }
        }
    }
    for(int j = 0;j < 26;j++){
        send(robot[j]);
    }
    vi p = wait();
    int ans = 0;
    for(int j = 0;j < 26;j++){
        if(p[j]){
            ans += (1 << j);
        }
    }
    return mp[ans];
}
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

avoid.cpp: In function 'void usaco_problem()':
avoid.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
avoid.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
avoid.cpp: In function 'void init()':
avoid.cpp:43:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
avoid.cpp:44:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 31752 KB Correct: 26 robot(s) used, 1 hour(s) passed

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 31760 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 31656 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 31788 KB Correct: 26 robot(s) used, 1 hour(s) passed
2 Correct 178 ms 31808 KB Correct: 26 robot(s) used, 1 hour(s) passed
3 Correct 190 ms 31836 KB Correct: 26 robot(s) used, 1 hour(s) passed
4 Correct 172 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
5 Correct 193 ms 31764 KB Correct: 26 robot(s) used, 1 hour(s) passed
6 Correct 164 ms 31828 KB Correct: 26 robot(s) used, 1 hour(s) passed
7 Correct 185 ms 31816 KB Correct: 26 robot(s) used, 1 hour(s) passed
8 Correct 176 ms 31724 KB Correct: 26 robot(s) used, 1 hour(s) passed
9 Correct 166 ms 31792 KB Correct: 26 robot(s) used, 1 hour(s) passed
10 Correct 201 ms 31636 KB Correct: 26 robot(s) used, 1 hour(s) passed
11 Correct 153 ms 31640 KB Correct: 26 robot(s) used, 1 hour(s) passed
12 Correct 158 ms 31764 KB Correct: 26 robot(s) used, 1 hour(s) passed
13 Correct 154 ms 31820 KB Correct: 26 robot(s) used, 1 hour(s) passed
14 Correct 160 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
15 Correct 149 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
16 Correct 151 ms 31696 KB Correct: 26 robot(s) used, 1 hour(s) passed
17 Correct 151 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
18 Correct 152 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
19 Correct 153 ms 31828 KB Correct: 26 robot(s) used, 1 hour(s) passed
20 Correct 151 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
21 Correct 161 ms 31820 KB Correct: 26 robot(s) used, 1 hour(s) passed
22 Correct 164 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
23 Correct 168 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
24 Correct 154 ms 31656 KB Correct: 26 robot(s) used, 1 hour(s) passed
25 Correct 150 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
26 Correct 152 ms 31636 KB Correct: 26 robot(s) used, 1 hour(s) passed
27 Correct 158 ms 31788 KB Correct: 26 robot(s) used, 1 hour(s) passed
28 Correct 156 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
29 Correct 158 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
30 Correct 150 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
31 Correct 156 ms 31700 KB Correct: 26 robot(s) used, 1 hour(s) passed
32 Correct 151 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
33 Correct 154 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
34 Correct 156 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
35 Correct 154 ms 31664 KB Correct: 26 robot(s) used, 1 hour(s) passed
36 Correct 172 ms 31748 KB Correct: 26 robot(s) used, 1 hour(s) passed
37 Correct 176 ms 31700 KB Correct: 26 robot(s) used, 1 hour(s) passed
38 Correct 173 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
39 Correct 171 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
40 Correct 156 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
41 Correct 165 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
42 Correct 158 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
43 Correct 158 ms 31628 KB Correct: 26 robot(s) used, 1 hour(s) passed
44 Correct 162 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
45 Correct 188 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
46 Correct 171 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
47 Correct 162 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
48 Correct 164 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
49 Correct 157 ms 31712 KB Correct: 26 robot(s) used, 1 hour(s) passed
50 Correct 155 ms 31708 KB Correct: 26 robot(s) used, 1 hour(s) passed
51 Correct 174 ms 31792 KB Correct: 26 robot(s) used, 1 hour(s) passed
52 Correct 184 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
53 Correct 167 ms 31676 KB Correct: 26 robot(s) used, 1 hour(s) passed
54 Correct 168 ms 31820 KB Correct: 26 robot(s) used, 1 hour(s) passed

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
2 Correct 169 ms 31608 KB Correct: 26 robot(s) used, 1 hour(s) passed
3 Correct 171 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
4 Correct 169 ms 31736 KB Correct: 26 robot(s) used, 1 hour(s) passed
5 Correct 159 ms 31820 KB Correct: 26 robot(s) used, 1 hour(s) passed
6 Correct 178 ms 31840 KB Correct: 26 robot(s) used, 1 hour(s) passed
7 Correct 155 ms 31652 KB Correct: 26 robot(s) used, 1 hour(s) passed
8 Correct 169 ms 31824 KB Correct: 26 robot(s) used, 1 hour(s) passed
9 Correct 178 ms 31832 KB Correct: 26 robot(s) used, 1 hour(s) passed
10 Correct 175 ms 31752 KB Correct: 26 robot(s) used, 1 hour(s) passed
11 Correct 166 ms 31816 KB Correct: 26 robot(s) used, 1 hour(s) passed
12 Correct 159 ms 31660 KB Correct: 26 robot(s) used, 1 hour(s) passed
13 Correct 170 ms 31828 KB Correct: 26 robot(s) used, 1 hour(s) passed
14 Correct 172 ms 31728 KB Correct: 26 robot(s) used, 1 hour(s) passed
15 Correct 162 ms 31600 KB Correct: 26 robot(s) used, 1 hour(s) passed