1966.md (8302B)
1 Source: https://codeforces.com/blog/entry/128914 2 3 [1966A - Card Exchange](/contest/1966/problem/A "Codeforces Round 941 (Div. 2)") 4 5 **Solution** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 t = int(input()) 13 14 for tc in range(t): 15 n, k = map(int, input().split()) 16 17 cards = list(map(int, input().split())) 18 ct = {} 19 20 ans = n 21 22 for c in cards: 23 if c in ct: 24 ct.update({c: ct[c] + 1}) 25 else: 26 ct.update({c: 1}) 27 if ct[c] >= k: 28 ans = k - 1 29 30 print(ans) 31 ``` 32 33 [1966B - Rectangle Filling](/contest/1966/problem/B "Codeforces Round 941 (Div. 2)") 34 35 **Solution** 36 37 Tutorial is loading... 38 39 **Code** 40 41 ``` 42 t = int(input()) 43 44 for tc in range(t): 45 n, m = map(int, input().split()) 46 gr = [] 47 48 for i in range(n): 49 gr.append(input()) 50 51 ans = "YES" 52 53 if gr[0][0] != gr[n - 1][m - 1]: 54 55 impossible = True 56 for j in range(m - 1): 57 if gr[0][j] != gr[0][j + 1] or gr[n - 1][j] != gr[n - 1][j + 1]: 58 impossible = False 59 60 if impossible: 61 ans = "NO" 62 63 impossible = True 64 for i in range(n - 1): 65 if gr[i][0] != gr[i + 1][0] or gr[i][m - 1] != gr[i + 1][m - 1]: 66 impossible = False 67 68 if impossible: 69 ans = "NO" 70 71 print(ans) 72 ``` 73 74 [1965A - Everything Nim](/contest/1965/problem/A "Codeforces Round 941 (Div. 1)") 75 76 **Solution** 77 78 Tutorial is loading... 79 80 **Code** 81 82 ``` 83 t = int(input()) 84 85 for tc in range(t): 86 87 n = int(input()) 88 a = list(map(int, input().split())) 89 90 maxsize = max(a) 91 92 a.sort() 93 mexsize = 1 94 for sz in a: 95 if sz == mexsize: 96 mexsize = mexsize + 1 97 98 if mexsize > maxsize: 99 print("Alice" if maxsize % 2 == 1 else "Bob") 100 else: 101 print("Alice" if mexsize % 2 == 1 else "Bob") 102 ``` 103 104 [1965B - Missing Subsequence Sum](/contest/1965/problem/B "Codeforces Round 941 (Div. 1)") 105 106 **Solution** 107 108 Tutorial is loading... 109 110 **Code** 111 112 ``` 113 t = int(input()) 114 115 for tc in range(t): 116 n, k = map(int, input().split()) 117 118 i = 0 119 while (1 << (i + 1)) <= k: 120 i = i + 1 121 122 ans = [k - (1 << i), k + 1, k + 1 + (1 << i)] 123 124 for j in range(20): 125 if j != i: 126 ans.append(1 << j); 127 128 print(len(ans)) 129 print(*ans) 130 ``` 131 132 [1965C - Folding Strip](/contest/1965/problem/C "Codeforces Round 941 (Div. 1)") 133 134 **Solution** 135 136 Tutorial is loading... 137 138 **Code** 139 140 ``` 141 t = int(input()) 142 143 for tc in range(t): 144 n = int(input()) 145 s = input() 146 mn = 0 147 mx = 0 148 cur = 0 149 150 for c in s: 151 152 if (cur % 2 == 0) == (c == '1'): 153 cur = cur + 1 154 else: 155 cur = cur - 1 156 157 mn = min(mn, cur) 158 mx = max(mx, cur) 159 160 print(mx - mn) 161 ``` 162 163 [1965D - Missing Subarray Sum](/contest/1965/problem/D "Codeforces Round 941 (Div. 1)") 164 165 **Solution** 166 167 Tutorial is loading... 168 169 **Code** 170 171 ``` 172 def getSubarraySums(a): 173 174 cts = [] 175 for i in range(len(a)): 176 sm = 0 177 for j in range(i, len(a)): 178 sm = sm + a[j] 179 cts.append(sm) 180 181 cts.sort() 182 return cts 183 184 def getOddOccurringElements(cts): 185 186 odds = [] 187 188 for ct in cts: 189 if len(odds) > 0 and ct == odds[-1]: 190 odds.pop() 191 else: 192 odds.append(ct) 193 return odds 194 195 def getPalindrome(odds, n): 196 197 a = [0] * n 198 prev = 0 199 idx = (n - 1) // 2 200 201 for x in odds: 202 if idx == n - 1 - idx: 203 a[idx] = x 204 else: 205 a[idx] = (x - prev) // 2 206 a[n - 1 - idx] = (x - prev) // 2 207 prev = x 208 idx = idx - 1 209 210 return a 211 212 def getLargestExcluded(bigList, smallList): 213 214 while len(smallList) > 0 and bigList[-1] == smallList[-1]: 215 bigList.pop() 216 smallList.pop() 217 return bigList[-1] 218 219 t = int(input()) 220 221 for tc in range(t): 222 223 n = int(input()) 224 225 subarraySums = list(map(int, input().split())) 226 subarraySums.sort() 227 odds = getOddOccurringElements(subarraySums) 228 229 missingSum = -1 230 231 if len(odds) > (n + 1) // 2: 232 233 oddvals = [] 234 evenvals = [] 235 for x in odds: 236 if x % 2 == 1: 237 oddvals.append(x) 238 else: 239 evenvals.append(x) 240 241 if len(evenvals) > 0 and len(oddvals) > 0: 242 243 missingSum = evenvals[0] if len(evenvals) == 1 else oddvals[0] 244 245 else: 246 247 b = getPalindrome(odds, n + 2) 248 bSums = getSubarraySums(b) 249 y = bSums[-1] 250 x = getLargestExcluded(bSums, subarraySums) 251 missingSum = 2 * x - y 252 253 else: 254 255 b = getPalindrome(odds, n - 2) 256 bSums = getSubarraySums(b) 257 y = bSums[-1] 258 x = getLargestExcluded(subarraySums, bSums) 259 missingSum = 2 * x - y 260 261 odds.append(missingSum) 262 odds.sort() 263 odds = getOddOccurringElements(odds) 264 265 ans = getPalindrome(odds, n) 266 print(*ans) 267 ``` 268 269 [1965E - Connected Cubes](/contest/1965/problem/E "Codeforces Round 941 (Div. 1)") 270 271 **Solution** 272 273 Tutorial is loading... 274 275 **Code** 276 277 ``` 278 n, m, k = map(int, input().split()) 279 a = [] 280 281 for i in range(n): 282 a.append(list(map(int, input().split()))) 283 284 ans = [] 285 286 for x in range(n): 287 for y in range(m): 288 for z in range(1, n + 1): 289 if y % 2 == 1: 290 ans.append([x, y, z, a[x][y]]) 291 else: 292 ans.append([x, y, z, a[min(x, n - z)][y]]) 293 for z in range(n + 1, n + k + 1): 294 if y % 2 == 1: 295 ans.append([x, y, z, a[x][y]]) 296 else: 297 ans.append([x, y, z, z - n]) 298 299 for x in range(n, n + k): 300 for y in range(m): 301 for z in range(1, n + 1): 302 if y % 2 == 1: 303 ans.append([x, y, z, x - n + 1]) 304 else: 305 ans.append([x, y, z, a[n - z][y]]) 306 ans.append([x, y, n + 1, x - n + 1]) 307 308 for y in range(m): 309 for z in range(n + 2, n + k + 1): 310 ans.append([n, y, z, z - n]) 311 312 for x in range(n + 1, n + k): 313 for z in range(n + 2, n + k + 1): 314 ans.append([x, 0, z, max(x - n + 1, z - n)]) 315 316 print(len(ans)) 317 318 for cube in ans: 319 print(cube[0] + 1, cube[1] + 1, cube[2] + 1, cube[3]) 320 ``` 321 322 [1965F - Conference](/contest/1965/problem/F "Codeforces Round 941 (Div. 1)") 323 324 **Solution** 325 326 Tutorial is loading... 327 328 **Code** 329 330 ``` 331 /** 332 * author: tourist 333 * created: 26.11.2023 09:36:38 334 **/ 335 #include <bits/stdc++.h> 336 337 using namespace std; 338 339 #ifdef LOCAL 340 #include "algo/debug.h" 341 #else 342 #define debug(...) 42 343 #endif 344 345 const long long inf = (long long) 1e18; 346 347 int main() { 348 ios::sync_with_stdio(false); 349 cin.tie(0); 350 int n; 351 cin >> n; 352 vector<long long> l(n), r(n); 353 for (int i = 0; i < n; i++) { 354 cin >> l[i] >> r[i]; 355 } 356 int original_n = n; 357 for (int rot = 0; rot < 2; rot++) { 358 // make all left ends distinct 359 map<long long, vector<long long>> mp; 360 for (int i = 0; i < n; i++) { 361 mp[l[i]].push_back(r[i]); 362 } 363 vector<long long> new_l, new_r; 364 auto it = mp.begin(); 365 multiset<long long> s; 366 long long T = -inf; 367 while (true) { 368 if (s.empty()) { 369 if (it == mp.end()) { 370 break; 371 } 372 T = it->first; 373 } 374 while (it != mp.end() && T == it->first) { 375 s.insert(it->second.begin(), it->second.end()); 376 ++it; 377 } 378 assert(!s.empty()); 379 new_l.push_back(T); 380 new_r.push_back(*s.begin()); 381 s.erase(s.begin()); 382 T += 1; 383 while (!s.empty() && *s.begin() < T) { 384 s.erase(s.begin()); 385 } 386 } 387 swap(l, new_l); 388 swap(r, new_r); 389 n = (int) l.size(); 390 for (int i = 0; i < n; i++) { 391 l[i] *= -1; 392 r[i] *= -1; 393 swap(l[i], r[i]); 394 } 395 } 396 sort(l.begin(), l.end()); 397 sort(r.begin(), r.end()); 398 vector<long long> ans(original_n + 1); 399 long long lx = -inf, rx = -inf; 400 int pl = 0, pr = 0; 401 int k = 0; 402 while (pl < n || pr < n) { 403 long long wait = min(pl < n ? l[pl] - lx : inf, pr < n ? r[pr] - rx : inf); 404 ans[k] += wait; 405 lx += wait; 406 rx += wait; 407 while (pl < n && l[pl] == lx) { 408 k += 1; 409 lx += 1; 410 pl += 1; 411 } 412 while (pr < n && r[pr] == rx) { 413 ans[k] += 1; 414 k -= 1; 415 rx += 1; 416 pr += 1; 417 } 418 } 419 for (int i = n; i > 1; i--) { 420 ans[i - 1] += ans[i]; 421 } 422 for (int i = 1; i <= original_n; i++) { 423 cout << ans[i] << '\n'; 424 } 425 return 0; 426 } 427 ```