1370.md (7266B)
1 Source: https://codeforces.com/blog/entry/79107 2 3 [1370A - Maximum GCD](/contest/1370/problem/A "Codeforces Round 651 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 #include < bits/stdc++.h > 13 using namespace std; 14 15 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 16 #define endl "\n" 17 #define int long long 18 19 const int N = 1e5 + 5; 20 21 int32_t main() 22 { 23 IOS; 24 int t; 25 cin >> t; 26 while(t--) 27 { 28 int n; 29 cin >> n; 30 cout << n / 2 << endl; 31 } 32 return 0; 33 } 34 ``` 35 36 This problem was prepared by [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Expert the_hyp0cr1t3") 37 38 [1370B - GCD Compression](/contest/1370/problem/B "Codeforces Round 651 (Div. 2)") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Code** 45 46 ``` 47 #include < bits/stdc++.h > 48 using namespace std; 49 50 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 51 #define endl "\n" 52 #define int long long 53 54 const int N = 2e5 + 5; 55 56 int n; 57 int a[N]; 58 59 int32_t main() 60 { 61 IOS; 62 int t; 63 cin >> t; 64 while(t--) 65 { 66 cin >> n; 67 vector< int > even, odd; 68 for(int i = 1; i <= 2 * n; i++) 69 { 70 cin >> a[i]; 71 if(a[i] % 2) 72 odd.push_back(i); 73 else 74 even.push_back(i); 75 } 76 vector< pair< int, int > > ans; 77 for(int i = 0; i + 1 < odd.size(); i += 2) 78 ans.push_back({odd[i], odd[i + 1]}); 79 for(int i = 0; i + 1 < even.size(); i += 2) 80 ans.push_back({even[i], even[i + 1]}); 81 for(int i = 0; i < n - 1; i++) 82 cout << ans[i].first << " " << ans[i].second << endl; 83 } 84 return 0; 85 } 86 ``` 87 88 This problem was prepared by [Ashishgup](/profile/Ashishgup "International Master Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10") 89 90 [1370C - Number Game](/contest/1370/problem/C "Codeforces Round 651 (Div. 2)") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Code** 97 98 ``` 99 #include< bits/stdc++.h > 100 using namespace std; 101 102 const int N = 50000; 103 104 void player_1(){ 105 cout << "Ashishgup" << endl; 106 } 107 108 void player_2(){ 109 cout << "FastestFinger" << endl; 110 } 111 112 bool check_prime(int n){ 113 for(int i = 2; i < min(N, n); i++) 114 if(n % i == 0) 115 return 0; 116 return 1; 117 } 118 119 int main(){ 120 int tc; 121 cin >> tc; 122 while(tc--){ 123 int n; 124 cin >> n; 125 bool lose = (n == 1); 126 if(n > 2 && n % 2 == 0){ 127 if((n & (n — 1)) == 0) 128 lose = 1; 129 else if(n % 4 != 0 && check_prime(n / 2)) 130 lose = 1; 131 } 132 if(lose) 133 player_2(); 134 else player_1(); 135 } 136 } 137 ``` 138 139 **Relevant Meme** 140 141  142 143 This problem was prepared by [FastestFinger](/profile/FastestFinger "Master FastestFinger") and [Ashishgup](/profile/Ashishgup "International Master Ashishgup") 144 145 [1370D - Odd-Even Subsequence](/contest/1370/problem/D "Codeforces Round 651 (Div. 2)") 146 147 **Tutorial** 148 149 Tutorial is loading... 150 151 **Code** 152 153 ``` 154 #include < bits/stdc++.h > 155 using namespace std; 156 157 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 158 #define endl "\n" 159 #define int long long 160 161 const int N = 2e5 + 5; 162 163 int n, k; 164 int a[N]; 165 166 bool check(int x, int cur) 167 { 168 int ans = 0; 169 for(int i = 1; i <= n; i++) 170 { 171 if(!cur) 172 { 173 ans++; 174 cur ^= 1; 175 } 176 else 177 { 178 if(a[i] <= x) 179 { 180 ans++; 181 cur ^= 1; 182 } 183 } 184 } 185 return ans >= k; 186 } 187 188 int binsearch(int lo, int hi) 189 { 190 while(lo < hi) 191 { 192 int mid = (lo + hi) / 2; 193 if(check(mid, 0) || check(mid, 1)) 194 hi = mid; 195 else 196 lo = mid + 1; 197 } 198 return lo; 199 } 200 201 int32_t main() 202 { 203 IOS; 204 cin >> n >> k; 205 for(int i = 1; i <= n; i++) 206 cin >> a[i]; 207 int ans = binsearch(1, 1e9); 208 cout << ans; 209 return 0; 210 } 211 ``` 212 213 This problem was prepared by [Ashishgup](/profile/Ashishgup "International Master Ashishgup") 214 215 [1370E - Binary Subsequence Rotation](/contest/1370/problem/E "Codeforces Round 651 (Div. 2)") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Code** 222 223 ``` 224 #include < bits/stdc++.h > 225 using namespace std; 226 227 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 228 #define endl "\n" 229 #define int long long 230 231 const int N = 1e6 + 5; 232 233 int n; 234 string s, t; 235 int a[N]; 236 237 int get(int x) 238 { 239 int cur = 0, mx = 0; 240 for(int i = 1; i <= n; i++) 241 { 242 cur += x * a[i]; 243 mx = max(mx, cur); 244 if(cur < 0) 245 cur = 0; 246 } 247 return mx; 248 } 249 250 int32_t main() 251 { 252 IOS; 253 cin >> n >> s >> t; 254 int sum = 0; 255 for(int i = 1; i <= n; i++) 256 { 257 if(s[i - 1] != t[i - 1]) 258 { 259 if(s[i - 1] == '1') 260 a[i] = -1; 261 else 262 a[i] = 1; 263 } 264 sum += a[i]; 265 } 266 if(sum != 0) 267 { 268 cout << -1; 269 return 0; 270 } 271 int ans = max(get(1), get(-1)); 272 cout << ans; 273 return 0; 274 } 275 ``` 276 277 This problem was prepared by [smartnj](/profile/smartnj "Candidate Master smartnj") 278 279 [1370F2 - The Hidden Pair (Hard Version)](/contest/1370/problem/F2 "Codeforces Round 651 (Div. 2)") 280 281 **Tutorial** 282 283 Tutorial is loading... 284 285 **Code** 286 287 ``` 288 #include< bits/stdc++.h > 289 using namespace std; 290 291 const int N = 1001; 292 293 vector< int > adj[N], depth(N), max_depth(N); 294 295 int n, root, dist; 296 297 void dfs(int i, int par){ 298 max_depth[i] = depth[i]; 299 for(int j : adj[i]){ 300 if(j == par) 301 continue; 302 depth[j] = 1 + depth[i], dfs(j, i); 303 max_depth[i] = max(max_depth[i], max_depth[j]); 304 } 305 } 306 307 void find_nodes(int i, int par, int req_depth, vector< int > &nodes){ 308 if(depth[i] == req_depth){ 309 nodes.push_back(i); 310 return; 311 } 312 for(int j : adj[i]) 313 if(j != par && max_depth[j] <= n / 2) 314 find_nodes(j, i, req_depth, nodes); 315 } 316 317 pair query(vector< int > nodes){ 318 cout << "? " << nodes.size() << ' '; 319 for(int i : nodes) 320 cout << i << ' '; 321 cout << endl; 322 fflush(stdout); 323 324 int x, dist; 325 cin >> x >> dist; 326 327 return {x, dist}; 328 } 329 330 int main(){ 331 int t; 332 cin >> t; 333 while(t--){ 334 cin >> n; 335 336 for(int i = 1; i <= n; i++) 337 adj[i].clear(), depth[i] = 0, max_depth[i] = 0; 338 339 for(int i = 1; i < n; i++){ 340 int u, v; 341 cin >> u >> v; 342 adj[u].push_back(v); 343 adj[v].push_back(u); 344 } 345 346 vector< int > nodes; 347 for(int i = 1; i <= n; i++) 348 nodes.push_back(i); 349 350 pair< int, int > res = query(nodes); 351 root = res.first, dist = res.second; 352 353 dfs(root, 0); 354 355 int st = 0, en = n / 2, first_node = root; 356 while(st <= en){ 357 int mid = st + en >> 1; 358 359 vector< int > node_set; 360 find_nodes(root, 0, mid, node_set); 361 362 if(node_set.empty()) 363 en = mid — 1; 364 else{ 365 pair< int, int > res = query(node_set); 366 if(res.second == dist) 367 first_node = res.first, st = mid + 1; 368 else en = mid — 1; 369 } 370 } 371 vector< int > candidate_second; 372 queue< pair< int, int > > q; 373 vector< int > vis(n + 1); 374 q.push({first_node, 0}); 375 while(!q.empty()){ 376 pair< int, int > node = q.front(); 377 q.pop(); 378 vis[node.first] = 1; 379 if(node.second == dist) 380 candidate_second.push_back(node.first); 381 382 for(int j : adj[node.first]) 383 if(!vis[j]) 384 vis[j] = 1, q.push({j, node.second + 1}); 385 } 386 pair< int, int > second_node = query(candidate_second); 387 cout << "! " << first_node << ' ' << second_node.first << endl; 388 389 string correct; 390 cin >> correct; 391 } 392 } 393 ``` 394 395 **Relevant Memes** 396 397  398 399  400 401  402 403 This problem was prepared by [FastestFinger](/profile/FastestFinger "Master FastestFinger") and [Ashishgup](/profile/Ashishgup "International Master Ashishgup") 404 405 Meme credits: [ridbit10](/profile/ridbit10 "Expert ridbit10") and [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Expert the_hyp0cr1t3") and [FastestFinger](/profile/FastestFinger "Master FastestFinger")