1837.md (7731B)
1 Source: https://codeforces.com/blog/entry/116752 2 3 [1837A - Grasshopper on a Line](/contest/1837/problem/A "Educational Codeforces Round 149 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 x, k = map(int, input().split()) 16 if x % k != 0: 17 print(1) 18 print(x) 19 else: 20 print(2) 21 print(1, x - 1) 22 ``` 23 24 [1837B - Comparison String](/contest/1837/problem/B "Educational Codeforces Round 149 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (BledDest)** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 int main() 40 { 41 ios_base::sync_with_stdio(0); 42 cin.tie(0); 43 int t; 44 cin >> t; 45 for(int i = 0; i < t; i++) 46 { 47 int n; 48 cin >> n; 49 string s; 50 cin >> s; 51 int ans = 1, cur = 1; 52 for(int i = 1; i < n; i++) 53 { 54 if(s[i] != s[i - 1]) cur = 1; 55 else cur++; 56 ans = max(ans, cur); 57 } 58 cout << ans + 1 << endl; 59 } 60 } 61 ``` 62 63 [1837C - Best Binary String](/contest/1837/problem/C "Educational Codeforces Round 149 (Rated for Div. 2)") 64 65 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution (Neon)** 72 73 ``` 74 #include <bits/stdc++.h> 75 76 using namespace std; 77 78 int main() { 79 ios::sync_with_stdio(false); cin.tie(0); 80 int t; 81 cin >> t; 82 while (t--) { 83 string s; 84 cin >> s; 85 char x = '0'; 86 for (auto& c : s) { 87 if (c == '?') c = x; 88 x = c; 89 } 90 cout << s << '\n'; 91 } 92 } 93 ``` 94 95 [1837D - Bracket Coloring](/contest/1837/problem/D "Educational Codeforces Round 149 (Rated for Div. 2)") 96 97 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 98 99 **Tutorial** 100 101 Tutorial is loading... 102 103 **Solution (BledDest)** 104 105 ``` 106 #include <bits/stdc++.h> 107 108 using namespace std; 109 110 int main() 111 { 112 ios_base::sync_with_stdio(0); 113 cin.tie(0); 114 int t; 115 cin >> t; 116 for(int i = 0; i < t; i++) 117 { 118 int n; 119 cin >> n; 120 string s; 121 cin >> s; 122 vector<int> bal(n + 1); 123 for(int j = 0; j < n; j++) 124 if(s[j] == '(') 125 bal[j + 1] = bal[j] + 1; 126 else 127 bal[j + 1] = bal[j] - 1; 128 129 if(bal.back() != 0) 130 cout << -1 << endl; 131 else 132 { 133 if(*min_element(bal.begin(), bal.end()) == 0 || *max_element(bal.begin(), bal.end()) == 0) 134 { 135 cout << 1 << endl; 136 for(int j = 0; j < n; j++) 137 { 138 if(j) cout << " "; 139 cout << 1; 140 } 141 cout << endl; 142 } 143 else 144 { 145 cout << 2 << endl; 146 vector<int> ans; 147 int cur = 0; 148 while(cur < n) 149 { 150 int w = (s[cur] == '(' ? 1 : 2); 151 do 152 { 153 cur++; 154 ans.push_back(w); 155 } 156 while(bal[cur] != 0); 157 } 158 for(int j = 0; j < n; j++) 159 { 160 if(j) cout << " "; 161 cout << ans[j]; 162 } 163 cout << endl; 164 } 165 } 166 } 167 } 168 ``` 169 170 [1837E - Playoff Fixing](/contest/1837/problem/E "Educational Codeforces Round 149 (Rated for Div. 2)") 171 172 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution (awoo)** 179 180 ``` 181 #include <bits/stdc++.h> 182 183 #define forn(i, n) for (int i = 0; i < int(n); i++) 184 185 using namespace std; 186 187 const int MOD = 998244353; 188 189 int main() { 190 int k; 191 scanf("%d", &k); 192 vector<int> a(1 << k); 193 forn(i, 1 << k){ 194 scanf("%d", &a[i]); 195 if (a[i] != -1) --a[i]; 196 } 197 int ans = 1; 198 for (int st = k - 1; st >= 0; --st){ 199 int big = 1 << st, fr = 0; 200 vector<int> na(1 << st); 201 forn(i, 1 << st){ 202 int mn = min(a[2 * i], a[2 * i + 1]); 203 int mx = max(a[2 * i], a[2 * i + 1]); 204 if (mn == -1){ 205 if (mx >= (1 << st)){ 206 --big; 207 na[i] = -1; 208 } 209 else if (mx != -1){ 210 na[i] = mx; 211 } 212 else{ 213 na[i] = -1; 214 ++fr; 215 } 216 continue; 217 } 218 if ((a[2 * i] < (1 << st)) == (a[2 * i + 1] < (1 << st))){ 219 puts("0"); 220 return 0; 221 } 222 na[i] = mn; 223 --big; 224 } 225 forn(_, fr) ans = ans * 2ll % MOD; 226 for (int i = 1; i <= big; ++i) ans = ans * 1ll * i % MOD; 227 a = na; 228 } 229 printf("%d\n", ans); 230 } 231 ``` 232 233 [1837F - Editorial for Two](/contest/1837/problem/F "Educational Codeforces Round 149 (Rated for Div. 2)") 234 235 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 236 237 **Tutorial** 238 239 Tutorial is loading... 240 241 **Solution 1 (awoo)** 242 243 ``` 244 #include <bits/stdc++.h> 245 246 #define forn(i, n) for (int i = 0; i < int(n); i++) 247 248 using namespace std; 249 250 int main() { 251 int t; 252 scanf("%d", &t); 253 while (t--){ 254 int n, k; 255 scanf("%d%d", &n, &k); 256 vector<int> a(n); 257 forn(i, n) scanf("%d", &a[i]); 258 259 vector<int> pr(n + 1), su(n + 1); 260 auto check = [&](long long x){ 261 forn(_, 2){ 262 priority_queue<int> cur; 263 pr[0] = 0; 264 long long cursum = 0; 265 forn(i, n){ 266 cur.push(a[i]); 267 cursum += a[i]; 268 while (cursum > x){ 269 cursum -= cur.top(); 270 cur.pop(); 271 } 272 pr[i + 1] = cur.size(); 273 } 274 reverse(a.begin(), a.end()); 275 swap(pr, su); 276 } 277 reverse(su.begin(), su.end()); 278 forn(i, n + 1) if (pr[i] + su[i] >= k) return true; 279 return false; 280 }; 281 282 long long l = 1, r = accumulate(a.begin(), a.end(), 0ll); 283 long long res = 0; 284 while (l <= r){ 285 long long m = (l + r) / 2; 286 if (check(m)){ 287 res = m; 288 r = m - 1; 289 } 290 else{ 291 l = m + 1; 292 } 293 } 294 printf("%lld\n", res); 295 } 296 } 297 ``` 298 299 **Solution 2 (awoo)** 300 301 ``` 302 #include <bits/stdc++.h> 303 304 #define forn(i, n) for (int i = 0; i < int(n); i++) 305 306 using namespace std; 307 308 int main() { 309 int t; 310 scanf("%d", &t); 311 while (t--){ 312 int n, k; 313 scanf("%d%d", &n, &k); 314 vector<int> a(n); 315 forn(i, n) scanf("%d", &a[i]); 316 vector<pair<int, int>> xs(n); 317 forn(i, n) xs[i] = {a[i], i}; 318 sort(xs.begin(), xs.end()); 319 forn(i, n) a[i] = lower_bound(xs.begin(), xs.end(), make_pair(a[i], i)) - xs.begin(); 320 321 vector<int> lstpr(n), lstsu(n); 322 forn(_, 2){ 323 set<int> cur; 324 forn(i, n){ 325 auto it = cur.insert(a[i]).first; 326 if (it == cur.begin()) 327 lstpr[i] = n; 328 else 329 lstpr[i] = *(--it); 330 } 331 swap(lstpr, lstsu); 332 reverse(a.begin(), a.end()); 333 } 334 335 vector<int> pr(n + 1), su(n + 1); 336 vector<int> prv(n + 2), nxt(n + 2); 337 338 auto check = [&](long long x){ 339 forn(_, 2){ 340 int cnt = 0; 341 prv[n + 1] = n; 342 nxt[n] = n + 1; 343 pr[0] = 0; 344 int mn = 1e9; 345 long long cursum = 0; 346 forn(i, n){ 347 if (mn < a[i]){ 348 pr[i + 1] = cnt; 349 continue; 350 } 351 nxt[a[i]] = nxt[lstpr[i]]; 352 prv[nxt[a[i]]] = a[i]; 353 prv[a[i]] = lstpr[i]; 354 nxt[prv[a[i]]] = a[i]; 355 cursum += xs[a[i]].first; 356 ++cnt; 357 while (cursum > x){ 358 mn = min(mn, prv[n + 1]); 359 cursum -= xs[prv[n + 1]].first; 360 prv[n + 1] = prv[prv[n + 1]]; 361 nxt[prv[n + 1]] = n + 1; 362 --cnt; 363 } 364 pr[i + 1] = cnt; 365 } 366 reverse(a.begin(), a.end()); 367 swap(lstpr, lstsu); 368 swap(pr, su); 369 } 370 reverse(su.begin(), su.end()); 371 forn(i, n + 1) if (pr[i] + su[i] >= k) return true; 372 return false; 373 }; 374 375 long long l = 1, r = 0; 376 for (int x : a) r += xs[x].first; 377 long long res = 0; 378 while (l <= r){ 379 long long m = (l + r) / 2; 380 if (check(m)){ 381 res = m; 382 r = m - 1; 383 } 384 else{ 385 l = m + 1; 386 } 387 } 388 printf("%lld\n", res); 389 } 390 } 391 ```