1463.md (7834B)
1 Source: https://codeforces.com/blog/entry/85707 2 3 [1463A - Dungeon](/contest/1463/problem/A "Educational Codeforces Round 100 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Ne0n25)** 12 13 ``` 14 for i in range(int(input())): 15 a, b, c = map(int, input().split()) 16 if (a + b + c) % 9 != 0: 17 print("NO") 18 else: 19 print("YES" if min(a, b, c) >= (a + b + c) // 9 else "NO") 20 ``` 21 22 [1463B - Find The Array](/contest/1463/problem/B "Educational Codeforces Round 100 (Rated for Div. 2)") 23 24 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (Ne0n25)** 31 32 ``` 33 for t in range(int(input())): 34 n = int(input()) 35 a = list(map(int, input().split())) 36 s = sum(a) 37 cur = [0, 0] 38 for i in range(n): 39 cur[i % 2] += a[i] - 1 40 for j in range(2): 41 if 2 * cur[j] > s: 42 continue 43 for i in range(n): 44 if i % 2 == j: 45 a[i] = 1 46 break 47 print(*a) 48 ``` 49 50 [1463C - Busy Robot](/contest/1463/problem/C "Educational Codeforces Round 100 (Rated for Div. 2)") 51 52 Idea: [KAN](/profile/KAN "Legendary Grandmaster KAN") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution (pikmike)** 59 60 ``` 61 def inside(l, r, x): 62 return min(l, r) <= x <= max(l, r) 63 64 def sg(x): 65 return -1 if x < 0 else int(x > 0) 66 67 for _ in range(int(input())): 68 n = int(input()) 69 qs = [] 70 for i in range(n): 71 qs.append(list(map(int, input().split()))) 72 qs.append([4*10**9, 0]) 73 ans = 0 74 pos, dr, lft = 0, 0, 0 75 for i in range(n): 76 t, x = qs[i] 77 tn = qs[i + 1][0] 78 if lft == 0: 79 lft = abs(pos - x) 80 dr = sg(x - pos) 81 tmp = min(lft, tn - t) 82 if inside(pos, pos + dr * tmp, x): 83 ans += 1 84 pos += dr * tmp 85 lft -= tmp 86 print(ans) 87 ``` 88 89 [1463D - Pairs](/contest/1463/problem/D "Educational Codeforces Round 100 (Rated for Div. 2)") 90 91 Idea: [adedalic](/profile/adedalic "International Master adedalic") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution 1 (adedalic)** 98 99 ``` 100 #include<bits/stdc++.h> 101 102 using namespace std; 103 104 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 105 #define sz(a) int((a).size()) 106 107 const int INF = int(1e9); 108 109 int n; 110 vector<int> b; 111 112 inline bool read() { 113 if(!(cin >> n)) 114 return false; 115 b.resize(n); 116 fore (i, 0, n) 117 cin >> b[i]; 118 return true; 119 } 120 121 bool ok(const vector<int> &a, const vector<int> &b, int cnt) { 122 fore (i, 0, cnt) { 123 if (a[i] >= b[sz(b) - cnt + i]) 124 return false; 125 } 126 return true; 127 } 128 129 inline void solve() { 130 vector<int> nb; 131 fore (i, 1, 2 * n + 1) { 132 if (!binary_search(b.begin(), b.end(), i)) 133 nb.push_back(i); 134 } 135 136 int mx[2] = {-1, -1}; 137 fore (k, 0, 2) { 138 int lf = 0, rg = n + 1; 139 while (rg - lf > 1) { 140 int mid = (lf + rg) / 2; 141 if (ok(b, nb, mid)) 142 lf = mid; 143 else 144 rg = mid; 145 } 146 mx[k] = lf; 147 if (!ok(nb, b, n - lf)) { 148 cout << 0 << endl; 149 return; 150 } 151 swap(b, nb); 152 } 153 154 assert(n - mx[1] <= mx[0]); 155 cout << mx[0] - (n - mx[1]) + 1 << endl; 156 } 157 158 int main() { 159 #ifdef _DEBUG 160 freopen("input.txt", "r", stdin); 161 int tt = clock(); 162 #endif 163 ios_base::sync_with_stdio(false); 164 cin.tie(0), cout.tie(0); 165 cout << fixed << setprecision(15); 166 167 int t; cin >> t; 168 while(t--) { 169 read(); 170 solve(); 171 172 #ifdef _DEBUG 173 cerr << "TIME = " << clock() - tt << endl; 174 tt = clock(); 175 #endif 176 } 177 return 0; 178 } 179 ``` 180 181 **Solution 2 (adedalic)** 182 183 ``` 184 #include<bits/stdc++.h> 185 186 using namespace std; 187 188 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 189 #define sz(a) int((a).size()) 190 191 const int INF = int(1e9); 192 193 int n; 194 vector<int> b; 195 196 inline bool read() { 197 if(!(cin >> n)) 198 return false; 199 b.resize(n); 200 fore (i, 0, n) 201 cin >> b[i]; 202 return true; 203 } 204 205 int getMax(const vector<int> &a, const vector<int> &b) { 206 int uk = 0; 207 fore (i, 0, sz(a)) { 208 while (uk < sz(b) && b[uk] < a[i]) 209 uk++; 210 if (uk >= sz(b)) 211 return i; 212 uk++; 213 } 214 return sz(a); 215 } 216 217 inline void solve() { 218 vector<int> nb; 219 fore (i, 1, 2 * n + 1) { 220 if (!binary_search(b.begin(), b.end(), i)) 221 nb.push_back(i); 222 } 223 224 int mxX = getMax(b, nb); 225 int mnX = n - getMax(nb, b); 226 227 cout << mxX - mnX + 1 << endl; 228 } 229 230 int main() { 231 #ifdef _DEBUG 232 freopen("input.txt", "r", stdin); 233 int tt = clock(); 234 #endif 235 ios_base::sync_with_stdio(false); 236 cin.tie(0), cout.tie(0); 237 cout << fixed << setprecision(15); 238 239 int t; cin >> t; 240 while(t--) { 241 read(); 242 solve(); 243 244 #ifdef _DEBUG 245 cerr << "TIME = " << clock() - tt << endl; 246 tt = clock(); 247 #endif 248 } 249 return 0; 250 } 251 ``` 252 253 [1463E - Plan of Lectures](/contest/1463/problem/E "Educational Codeforces Round 100 (Rated for Div. 2)") 254 255 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 256 257 **Tutorial** 258 259 Tutorial is loading... 260 261 **Solution (pikmike)** 262 263 ``` 264 #include <bits/stdc++.h> 265 266 using namespace std; 267 268 #define forn(i, n) for(int i = 0; i < int(n); i++) 269 270 vector<vector<int>> g, h, ng; 271 272 vector<int> rk, p; 273 274 int getp(int a){ 275 return a == p[a] ? a : p[a] = getp(p[a]); 276 } 277 278 void unite(int a, int b){ 279 a = getp(a), b = getp(b); 280 if (a == b) return; 281 if (rk[a] < rk[b]) swap(a, b); 282 rk[a] += rk[b]; 283 p[b] = a; 284 } 285 286 vector<vector<int>> comp; 287 288 vector<int> ord; 289 vector<int> used; 290 bool fl; 291 292 void ts(int v, const vector<vector<int>> &g){ 293 used[v] = 1; 294 for (int u : g[v]){ 295 if (used[u] == 0) 296 ts(u, g); 297 else if (used[u] == 1) 298 fl = false; 299 if (!fl) return; 300 } 301 ord.push_back(v); 302 used[v] = 2; 303 } 304 305 bool topsort(const vector<vector<int>> &g){ 306 int n = g.size(); 307 used.assign(n, 0); 308 ord.clear(); 309 fl = true; 310 forn(i, n) if (!used[i]){ 311 ts(i, g); 312 if (!fl) return false; 313 } 314 reverse(ord.begin(), ord.end()); 315 return true; 316 } 317 318 vector<int> pos; 319 320 bool dfs(int v){ 321 for (int u : g[v]){ 322 if (pos[u] < pos[v]) 323 return false; 324 if (!dfs(u)) 325 return false; 326 } 327 return true; 328 } 329 330 int main() { 331 int n, m; 332 scanf("%d%d", &n, &m); 333 g.resize(n); 334 h.resize(n); 335 ng.resize(n); 336 int rt = -1; 337 forn(i, n){ 338 int p; 339 scanf("%d", &p); 340 --p; 341 if (p == -1) 342 rt = i; 343 else 344 g[p].push_back(i); 345 } 346 rk.assign(n, 1); 347 p.resize(n); 348 iota(p.begin(), p.end(), 0); 349 forn(i, m){ 350 int v, u; 351 scanf("%d%d", &v, &u); 352 --v, --u; 353 h[v].push_back(u); 354 unite(v, u); 355 } 356 if (!topsort(h)){ 357 puts("0"); 358 return 0; 359 } 360 auto ord1 = ord; 361 vector<int> pos1(n); 362 forn(i, n) pos1[ord1[i]] = i; 363 forn(v, n) for (int u : g[v]) if (getp(v) != getp(u)) 364 ng[getp(v)].push_back(getp(u)); 365 if (!topsort(ng)){ 366 puts("0"); 367 return 0; 368 } 369 comp.resize(n); 370 forn(i, n) comp[getp(i)].push_back(i); 371 vector<int> fin; 372 for (int it : ord){ 373 sort(comp[it].begin(), comp[it].end(), [&](int v, int u){ return pos1[v] < pos1[u]; }); 374 for (int v : comp[it]) 375 fin.push_back(v); 376 } 377 pos.resize(n); 378 forn(i, n) pos[fin[i]] = i; 379 if (!dfs(rt)){ 380 puts("0"); 381 return 0; 382 } 383 for (int v : fin) 384 printf("%d ", v + 1); 385 puts(""); 386 } 387 ``` 388 389 [1463F - Max Correct Set](/contest/1463/problem/F "Educational Codeforces Round 100 (Rated for Div. 2)") 390 391 Idea: [Neon](/profile/Neon "Candidate Master Neon") 392 393 **Tutorial** 394 395 Tutorial is loading... 396 397 **Solution (Ne0n25)** 398 399 ``` 400 #include <bits/stdc++.h> 401 402 using namespace std; 403 404 const int INF = 1e9; 405 const int N = 22; 406 407 int dp[2][1 << N]; 408 int val[2 * N]; 409 410 int main() { 411 int n, x, y; 412 scanf("%d%d%d", &n, &x, &y); 413 414 int k = x + y; 415 int m = max(x, y); 416 int FULL = (1 << m) - 1; 417 418 for (int i = 0; i < k; ++i) 419 val[i] = n / k + (i < n % k); 420 for (int mask = 0; mask < (1 << m); ++mask) 421 dp[0][mask] = -INF; 422 dp[0][0] = 0; 423 424 for (int i = 0; i < k; ++i) { 425 for (int mask = 0; mask < (1 << m); ++mask) 426 dp[1][mask] = -INF; 427 for (int mask = 0; mask < (1 << m); ++mask) { 428 if (dp[0][mask] == -INF) 429 continue; 430 int nmask = (mask << 1) & FULL; 431 dp[1][nmask] = max(dp[1][nmask], dp[0][mask]); 432 if (((mask >> (x - 1)) & 1) | ((mask >> (y - 1)) & 1)) 433 continue; 434 nmask |= 1; 435 dp[1][nmask] = max(dp[1][nmask], dp[0][mask] + val[i]); 436 } 437 swap(dp[0], dp[1]); 438 } 439 440 int ans = 0; 441 for (int mask = 0; mask < (1 << m); ++mask) 442 ans = max(ans, dp[0][mask]); 443 printf("%d\n", ans); 444 } 445 ```