1006.md (7102B)
1 Source: https://codeforces.com/blog/entry/60672 2 3 [1006A - Adjacent Replacements](/contest/1006/problem/A "Codeforces Round 498 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int n; 23 cin >> n; 24 for (int i = 0; i < n; ++i) { 25 int x; 26 cin >> x; 27 cout << x - !(x & 1) << " "; 28 } 29 30 return 0; 31 } 32 ``` 33 34 [1006B - Polycarp's Practice](/contest/1006/problem/B "Codeforces Round 498 (Div. 3)") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (Vovuh)** 41 42 ``` 43 #include <bits/stdc++.h> 44 45 using namespace std; 46 47 int main() { 48 #ifdef _DEBUG 49 freopen("input.txt", "r", stdin); 50 // freopen("output.txt", "w", stdout); 51 #endif 52 53 int n, k; 54 cin >> n >> k; 55 vector<pair<int, int>> res(n); 56 vector<int> a(n); 57 for (int i = 0; i < n; ++i) { 58 cin >> res[i].first; 59 a[i] = res[i].first; 60 res[i].second = i + 1; 61 } 62 63 sort(res.begin(), res.end()); 64 reverse(res.begin(), res.end()); 65 sort(res.begin(), res.begin() + k, [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; }); 66 67 int lst = 0, sum = 0; 68 for (int i = 0; i < k - 1; ++i) { 69 sum += *max_element(a.begin() + lst, a.begin() + res[i].second); 70 lst = res[i].second; 71 } 72 sum += *max_element(a.begin() + lst, a.end()); 73 cout << sum << endl; 74 75 76 lst = 0; 77 for (int i = 0; i < k - 1; ++i) { 78 cout << res[i].second - lst << " "; 79 lst = res[i].second; 80 } 81 cout << n - lst << endl; 82 83 return 0; 84 } 85 ``` 86 87 [1006C - Three Parts of the Array](/contest/1006/problem/C "Codeforces Round 498 (Div. 3)") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution (Vovuh, set)** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 int main() { 101 #ifdef _DEBUG 102 freopen("input.txt", "r", stdin); 103 // freopen("output.txt", "w", stdout); 104 #endif 105 106 int n; 107 cin >> n; 108 vector<int> a(n); 109 for (int i = 0; i < n; ++i) 110 cin >> a[i]; 111 112 set<long long> sum; 113 long long l = 0; 114 for (int i = 0; i < n; ++i) { 115 l += a[i]; 116 sum.insert(l); 117 } 118 119 long long ans = 0; 120 long long r = 0; 121 for (int i = n - 1; i >= 0; --i) { 122 sum.erase(l); 123 l -= a[i]; 124 r += a[i]; 125 if (sum.count(r)) 126 ans = max(ans, r); 127 } 128 129 cout << ans << endl; 130 131 return 0; 132 } 133 ``` 134 135 **Solution (ivan100sic, two pointers)** 136 137 ``` 138 #include <bits/stdc++.h> 139 using namespace std; 140 141 typedef long long ll; 142 typedef unsigned long long ull; 143 typedef long double ld; 144 145 int n; 146 int a[200005]; 147 148 int main() { 149 ios_base::sync_with_stdio(false); 150 cin.tie(nullptr); 151 cout.tie(nullptr); 152 cerr.tie(nullptr); 153 154 cin >> n; 155 for (int i=1; i<=n; i++) 156 cin >> a[i]; 157 158 int i = 0, j = n+1; 159 ll zi = 0, zj = 0, solidx = 0; 160 while (i < j) { 161 if (zi < zj) 162 zi += a[++i]; 163 else if (zi > zj) 164 zj += a[--j]; 165 else { 166 solidx = i; 167 zi += a[++i]; 168 zj += a[--j]; 169 } 170 } 171 172 cout << accumulate(a+1, a+solidx+1, 0ll); // here 173 } 174 ``` 175 176 [1006D - Two Strings Swaps](/contest/1006/problem/D "Codeforces Round 498 (Div. 3)") 177 178 **Tutorial** 179 180 Tutorial is loading... 181 182 **Solution (Ne0n25)** 183 184 ``` 185 #include <bits/stdc++.h> 186 187 using namespace std; 188 189 #define x first 190 #define y second 191 #define mp make_pair 192 #define pb push_back 193 #define sqr(a) ((a) * (a)) 194 #define sz(a) int(a.size()) 195 #define all(a) a.begin(), a.end() 196 #define forn(i, n) for(int i = 0; i < int(n); i++) 197 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 198 199 typedef long long li; 200 typedef long double ld; 201 typedef pair<int, int> pt; 202 203 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) { 204 return out << "(" << a.x << ", " << a.y << ")"; 205 } 206 207 template <class A> ostream& operator << (ostream& out, const vector<A> &v) { 208 out << "["; 209 forn(i, sz(v)) { 210 if(i) out << ", "; 211 out << v[i]; 212 } 213 return out << "]"; 214 } 215 216 mt19937 rnd(time(NULL)); 217 218 const int INF = int(1e9); 219 const li INF64 = li(1e18); 220 const int MOD = INF + 7; 221 const ld EPS = 1e-9; 222 const ld PI = acos(-1.0); 223 224 int n; 225 string s, t; 226 227 bool read() { 228 if (!(cin >> n >> s >> t)) 229 return false; 230 return true; 231 } 232 233 void solve() { 234 int ans = 0; 235 forn(i, n / 2) { 236 map<char, int> a; 237 a[s[i]]++; a[s[n - i - 1]]++; 238 a[t[i]]++; a[t[n - i - 1]]++; 239 if (sz(a) == 4) 240 ans += 2; 241 else if (sz(a) == 3) 242 ans += 1 + (s[i] == s[n - i - 1]); 243 else if (sz(a) == 2) 244 ans += a[s[i]] != 2; 245 } 246 247 if (n % 2 == 1 && s[n / 2] != t[n / 2]) 248 ans++; 249 250 cout << ans << endl; 251 } 252 253 int main() { 254 #ifdef _DEBUG 255 freopen("input.txt", "r", stdin); 256 // freopen("output.txt", "w", stdout); 257 258 int tt = clock(); 259 260 #endif 261 262 cerr.precision(15); 263 cout.precision(15); 264 cerr << fixed; 265 cout << fixed; 266 267 #ifdef _DEBUG 268 while (read()) { 269 #else 270 if (read()) { 271 #endif 272 solve(); 273 274 #ifdef _DEBUG 275 cerr << "TIME = " << clock() - tt << endl; 276 tt = clock(); 277 #endif 278 279 } 280 } 281 ``` 282 283 [1006E - Military Problem](/contest/1006/problem/E "Codeforces Round 498 (Div. 3)") 284 285 **Tutorial** 286 287 Tutorial is loading... 288 289 **Solution (mareksom)** 290 291 ``` 292 #include <bits/stdc++.h> 293 294 using namespace std; 295 296 int n, q; 297 vector<vector<int>> tree; 298 299 int current_preorder; 300 vector<int> preorder, max_preorder; 301 vector<int> sorted_by_preorder; 302 303 void Dfs(int w) { 304 sorted_by_preorder[current_preorder] = w; 305 preorder[w] = current_preorder++; 306 for (int c : tree[w]) { 307 Dfs(c); 308 } 309 max_preorder[w] = current_preorder - 1; 310 } 311 312 int main() { 313 ios_base::sync_with_stdio(0); 314 cin.tie(0); 315 cin >> n >> q; 316 assert(2 <= n); 317 assert(1 <= q); 318 tree.resize(n); 319 for (int i = 1; i < n; i++) { 320 int p; 321 cin >> p; 322 p--; 323 assert(0 <= p and p < n); 324 tree[p].push_back(i); 325 } 326 327 preorder.resize(n); 328 max_preorder.resize(n); 329 sorted_by_preorder.resize(n); 330 current_preorder = 0; 331 Dfs(0); 332 333 for (int i = 0; i < q; i++) { 334 int u, k; 335 cin >> u >> k; 336 u--; k--; 337 assert(0 <= u and u < n); 338 assert(0 <= k and k < n); 339 k += preorder[u]; 340 int answer = -1; 341 if (k <= max_preorder[u]) { 342 answer = sorted_by_preorder[k] + 1; 343 assert(1 <= answer and answer <= n); 344 } 345 cout << answer << '\n'; 346 } 347 return 0; 348 } 349 ``` 350 351 [1006F - Xor-Paths](/contest/1006/problem/F "Codeforces Round 498 (Div. 3)") 352 353 **Tutorial** 354 355 Tutorial is loading... 356 357 **Solution (Vovuh)** 358 359 ``` 360 #include <bits/stdc++.h> 361 362 using namespace std; 363 364 const int N = 20; 365 366 map<long long, int> v[N][N]; 367 368 int n, m; 369 int half; 370 long long k; 371 long long a[N][N]; 372 long long ans; 373 374 void calclf(int x, int y, long long val, int cnt) { 375 val ^= a[x][y]; 376 if (cnt == half) { 377 ++v[x][y][val]; 378 return; 379 } 380 if (x + 1 < n) 381 calclf(x + 1, y, val, cnt + 1); 382 if (y + 1 < m) 383 calclf(x, y + 1, val, cnt + 1); 384 } 385 386 void calcrg(int x, int y, long long val, int cnt) { 387 if (cnt == n + m - 2 - half) { 388 if (v[x][y].count(k ^ val)) 389 ans += v[x][y][k ^ val]; 390 return; 391 } 392 if (x > 0) 393 calcrg(x - 1, y, val ^ a[x][y], cnt + 1); 394 if (y > 0) 395 calcrg(x, y - 1, val ^ a[x][y], cnt + 1); 396 } 397 398 int main() { 399 #ifdef _DEBUG 400 freopen("input.txt", "r", stdin); 401 // freopen("output.txt", "w", stdout); 402 #endif 403 404 cin >> n >> m >> k; 405 half = (n + m - 2) / 2; 406 for (int i = 0; i < n; ++i) { 407 for (int j = 0; j < m; ++j) { 408 cin >> a[i][j]; 409 } 410 } 411 412 calclf(0, 0, 0, 0); 413 calcrg(n - 1, m - 1, 0, 0); 414 415 cout << ans << endl; 416 417 return 0; 418 } 419 ```