1923.md (8518B)
1 Source: https://codeforces.com/blog/entry/126339 2 3 [1923A - Moving Chips](/contest/1923/problem/A "Educational Codeforces Round 162 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 a = list(map(int, input().split())) 18 l, r = a.index(1), n - a[::-1].index(1) - 1 19 c = a.count(1) 20 print(r - l - c + 1) 21 ``` 22 23 [1923B - Monsters Attack!](/contest/1923/problem/B "Educational Codeforces Round 162 (Rated for Div. 2)") 24 25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (Neon)** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 using namespace std; 37 38 int main() { 39 int t; 40 cin >> t; 41 while (t--) { 42 int n, k; 43 cin >> n >> k; 44 vector<int> a(n), x(n); 45 for (auto& it : a) cin >> it; 46 for (auto& it : x) cin >> it; 47 vector<long long> s(n + 1); 48 for (int i = 0; i < n; ++i) s[abs(x[i])] += a[i]; 49 bool ok = true; 50 long long lft = 0; 51 for (int i = 1; i <= n; ++i) { 52 lft += k - s[i]; 53 ok &= (lft >= 0); 54 } 55 cout << (ok ? "YES" : "NO") << '\n'; 56 } 57 } 58 ``` 59 60 [1923C - Find B](/contest/1923/problem/C "Educational Codeforces Round 162 (Rated for Div. 2)") 61 62 Idea: [Roms](/profile/Roms "Master Roms") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (Roms)** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 using namespace std; 74 75 const int N = 300043; 76 77 int t; 78 int n, m; 79 int a[N]; 80 long long sum[N]; 81 int cnt1[N]; 82 83 int main() { 84 ios_base::sync_with_stdio(false); 85 86 cin >> t; 87 for (int tc = 0; tc < t; ++tc) { 88 cin >> n >> m; 89 memset(sum, 0, sizeof(sum[0]) * (n + 5)); 90 memset(cnt1, 0, sizeof(cnt1[0]) * (n + 5)); 91 for (int i = 0; i < n; ++i) { 92 cin >> a[i]; 93 sum[i + 1] = sum[i] + a[i]; 94 cnt1[i + 1] = cnt1[i] + (a[i] == 1); 95 } 96 97 for (int i = 0; i < m; ++i) { 98 int l, r; 99 cin >> l >> r; 100 --l; 101 int cur_cnt1 = cnt1[r] - cnt1[l]; 102 long long cur_sum = sum[r] - sum[l]; 103 104 if((r - l) + cur_cnt1 <= cur_sum && r - l > 1) 105 cout << "YES\n"; 106 else 107 cout << "NO\n"; 108 } 109 } 110 return 0; 111 } 112 ``` 113 114 [1923D - Slimes](/contest/1923/problem/D "Educational Codeforces Round 162 (Rated for Div. 2)") 115 116 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 117 118 **Tutorial** 119 120 Tutorial is loading... 121 122 **Solution (Neon)** 123 124 ``` 125 #include <bits/stdc++.h> 126 127 using namespace std; 128 129 int main() { 130 int t; 131 cin >> t; 132 while (t--) { 133 int n; 134 cin >> n; 135 vector<int> a(n); 136 for (auto& x : a) cin >> x; 137 vector<int> ans(n, n); 138 for (int z = 0; z < 2; ++z) { 139 vector<long long> s(n + 1); 140 for (int i = 0; i < n; ++i) s[i + 1] = s[i] + a[i]; 141 vector<int> p(n, -1); 142 for (int i = 1; i < n; ++i) { 143 int j = (z ? n - i - 1 : i); 144 int l = 1, r = i; 145 while (l <= r) { 146 int m = (l + r) / 2; 147 if (s[i] - s[i - m] > a[i] && p[i - 1] >= i - m) { 148 ans[j] = min(ans[j], m); 149 r = m - 1; 150 } else { 151 l = m + 1; 152 } 153 } 154 if (a[i - 1] > a[i]) ans[j] = 1; 155 p[i] = (a[i] == a[i - 1] ? p[i - 1] : i - 1); 156 } 157 reverse(a.begin(), a.end()); 158 } 159 for (int i = 0; i < n; ++i) 160 cout << (ans[i] == n ? -1 : ans[i]) << ' '; 161 cout << '\n'; 162 } 163 } 164 ``` 165 166 [1923E - Count Paths](/contest/1923/problem/E "Educational Codeforces Round 162 (Rated for Div. 2)") 167 168 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 169 170 **Tutorial** 171 172 Tutorial is loading... 173 174 **Solution (awoo)** 175 176 ``` 177 #include <bits/stdc++.h> 178 179 #define forn(i, n) for (int i = 0; i < int(n); i++) 180 181 using namespace std; 182 183 int n; 184 vector<int> a; 185 vector<vector<int>> g; 186 187 long long ans; 188 vector<map<int, int>> cnt; 189 190 void dfs(int v, int p = -1){ 191 int bst = -1; 192 for (int u : g[v]) if (u != p){ 193 dfs(u, v); 194 if (bst == -1 || cnt[bst].size() < cnt[u].size()) 195 bst = u; 196 } 197 for (int u : g[v]) if (u != p && u != bst){ 198 for (auto it : cnt[u]){ 199 int x = it.first, y = it.second; 200 if (x != a[v]) ans += cnt[bst][x] * 1ll * y; 201 cnt[bst][x] += y; 202 } 203 } 204 if (bst != -1) swap(cnt[bst], cnt[v]); 205 ans += cnt[v][a[v]]; 206 cnt[v][a[v]] = 1; 207 } 208 209 int main() { 210 cin.tie(0); 211 ios::sync_with_stdio(false); 212 int t; 213 cin >> t; 214 while (t--){ 215 int n; 216 cin >> n; 217 a.resize(n); 218 forn(i, n) cin >> a[i]; 219 g.assign(n, {}); 220 forn(_, n - 1){ 221 int v, u; 222 cin >> v >> u; 223 --v, --u; 224 g[v].push_back(u); 225 g[u].push_back(v); 226 } 227 ans = 0; 228 cnt.assign(n, {}); 229 dfs(0); 230 cout << ans << '\n'; 231 } 232 return 0; 233 } 234 ``` 235 236 [1923F - Shrink-Reverse](/contest/1923/problem/F "Educational Codeforces Round 162 (Rated for Div. 2)") 237 238 Idea: [adedalic](/profile/adedalic "International Master adedalic") 239 240 **Tutorial** 241 242 Tutorial is loading... 243 244 **Solution (adedalic)** 245 246 ``` 247 #include<bits/stdc++.h> 248 249 using namespace std; 250 251 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 252 #define sz(a) int((a).size()) 253 #define all(a) (a).begin(), (a).end() 254 255 typedef long long li; 256 typedef pair<int, int> pt; 257 258 const int INF = int(1e9); 259 const int MOD = int(1e9) + 7; 260 261 int add(int a, int b) { 262 a += b; 263 if (a >= MOD) 264 a -= MOD; 265 return a; 266 } 267 int mul(int a, int b) { 268 return int(a * 1ll * b % MOD); 269 } 270 271 namespace SuffixArray { 272 string s; 273 vector< array<int, 2> > classes; 274 275 vector<int> build(const string &bs) { 276 s = bs; 277 s += '$'; 278 279 vector<int> c(all(s)), ord(sz(s)); 280 iota(all(ord), 0); 281 classes.resize(sz(s)); 282 283 for (int len = 1; len < 2 * sz(s); len <<= 1) { 284 int half = len >> 1; 285 fore (i, 0, sz(s)) 286 classes[i] = {c[i], c[(i + half) % sz(s)]}; 287 288 sort(all(ord), [&](int i, int j) { 289 return classes[i] < classes[j]; 290 }); 291 c[ord[0]] = 0; 292 fore (i, 1, sz(ord)) 293 c[ord[i]] = c[ord[i - 1]] + (classes[ord[i - 1]] != classes[ord[i]]); 294 } 295 296 c.pop_back(); 297 for (int &cc : c) 298 cc--; 299 return c; 300 } 301 }; 302 303 int n, k; 304 string s; 305 306 inline bool read() { 307 if(!(cin >> n >> k)) 308 return false; 309 cin >> s; 310 return true; 311 } 312 313 string calcZero(string s) { 314 int rem = k; 315 int pos = 0; 316 for (int i = sz(s) - 1; rem > 0 && i >= 0; i--) { 317 if (s[i] == '1') 318 continue; 319 320 while (pos < sz(s) && s[pos] == '0') 321 pos++; 322 if (pos >= i) 323 break; 324 325 swap(s[pos], s[i]); 326 rem--; 327 } 328 return s.substr(s.find('1')); 329 } 330 331 string calcOne(string s) { 332 reverse(all(s)); 333 334 auto c = SuffixArray::build(s); 335 int cntOnes = count(all(s), '1'); 336 337 array<int, 3> mn = { 2 * sz(s), INF, -1 }; 338 339 int u = 0, curOnes = 0; 340 fore (i, 0, n) { 341 while (u < sz(s) && (u - i < cntOnes || cntOnes - curOnes > k - 1)) { 342 curOnes += s[u] == '1'; 343 u++; 344 } 345 if (u - i < cntOnes || cntOnes - curOnes > k - 1) 346 break; 347 348 array<int, 3> curAns = { u - i, c[i], i }; 349 mn = min(mn, curAns); 350 351 curOnes -= s[i] == '1'; 352 } 353 assert(mn[2] >= 0); 354 355 string res = s.substr(mn[2], mn[0]); 356 int toAdd = cntOnes - count(all(res), '1'); 357 for (int i = sz(res) - 1; toAdd > 0 && i >= 0; i--) { 358 if (res[i] == '0') { 359 res[i] = '1'; 360 toAdd--; 361 } 362 } 363 return res; 364 } 365 366 inline void solve() { 367 auto s1 = calcZero(s); 368 auto s2 = calcOne(s); 369 370 if (sz(s1) > sz(s2) || (sz(s1) == sz(s2) && s1 > s2)) 371 swap(s1, s2); 372 373 int res = 0; 374 for (char c : s1) 375 res = add(mul(res, 2), c - '0'); 376 cout << res << endl; 377 } 378 379 int main() { 380 #ifdef _DEBUG 381 freopen("input.txt", "r", stdin); 382 int tt = clock(); 383 #endif 384 ios_base::sync_with_stdio(false); 385 cin.tie(0), cout.tie(0); 386 cout << fixed << setprecision(15); 387 388 if(read()) { 389 solve(); 390 391 #ifdef _DEBUG 392 cerr << "TIME = " << clock() - tt << endl; 393 tt = clock(); 394 #endif 395 } 396 return 0; 397 } 398 ```