1102.md (6995B)
1 Source: https://codeforces.com/blog/entry/64439 2 3 [1102A - Integer Sequence Dividing](/contest/1102/problem/A "Codeforces Round 531 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution 1** 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 n %= 4; 25 if (n == 0 || n == 3) { 26 cout << 0 << endl; 27 } else { 28 cout << 1 << endl; 29 } 30 31 return 0; 32 } 33 ``` 34 35 **Solution 2** 36 37 ``` 38 #include <bits/stdc++.h> 39 40 using namespace std; 41 42 int main() { 43 #ifdef _DEBUG 44 freopen("input.txt", "r", stdin); 45 // freopen("output.txt", "w", stdout); 46 #endif 47 48 int n; 49 cin >> n; 50 long long sum = n * 1ll * (n + 1) / 2; 51 cout << (sum & 1) << endl; 52 53 return 0; 54 } 55 ``` 56 57 [1102B - Array K-Coloring](/contest/1102/problem/B "Codeforces Round 531 (Div. 3)") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution** 64 65 ``` 66 #include <bits/stdc++.h> 67 68 using namespace std; 69 70 int main() { 71 #ifdef _DEBUG 72 freopen("input.txt", "r", stdin); 73 // freopen("output.txt", "w", stdout); 74 #endif 75 76 int n, k; 77 cin >> n >> k; 78 vector<pair<int, int>> a(n); 79 for (int i = 0; i < n; ++i) { 80 cin >> a[i].first; 81 a[i].second = i; 82 } 83 84 sort(a.begin(), a.end()); 85 86 vector<vector<int>> buckets(k); 87 vector<int> res(n); 88 for (int i = 0; i < n; ++i) { 89 buckets[i % k].push_back(a[i].first); 90 res[a[i].second] = i % k; 91 } 92 93 for (int i = 0; i < k; ++i) { 94 for (int j = 0; j < int(buckets[i].size()) - 1; ++j) { 95 if (buckets[i][j] == buckets[i][j + 1]) { 96 cout << "NO" << endl; 97 return 0; 98 } 99 } 100 } 101 102 cout << "YES" << endl; 103 for (int i = 0; i < n; ++i) { 104 cout << res[i] + 1 << " "; 105 } 106 cout << endl; 107 108 return 0; 109 } 110 ``` 111 112 [1102C - Doors Breaking and Repairing](/contest/1102/problem/C "Codeforces Round 531 (Div. 3)") 113 114 **Tutorial** 115 116 Tutorial is loading... 117 118 **Solution** 119 120 ``` 121 #include <bits/stdc++.h> 122 123 using namespace std; 124 125 int main() { 126 #ifdef _DEBUG 127 freopen("input.txt", "r", stdin); 128 // freopen("output.txt", "w", stdout); 129 #endif 130 131 int n, x, y; 132 cin >> n >> x >> y; 133 int cnt = 0; 134 for (int i = 0; i < n; ++i) { 135 int cur; 136 cin >> cur; 137 if (cur <= x) { 138 ++cnt; 139 } 140 } 141 142 if (x > y) { 143 cout << n << endl; 144 } else { 145 cout << (cnt + 1) / 2 << endl; 146 } 147 148 return 0; 149 } 150 ``` 151 152 [1102D - Balanced Ternary String](/contest/1102/problem/D "Codeforces Round 531 (Div. 3)") 153 154 **Tutorial** 155 156 Tutorial is loading... 157 158 **Solution (Vovuh)** 159 160 ``` 161 #include <bits/stdc++.h> 162 163 using namespace std; 164 165 int n; 166 167 int needRep(const vector<int> &cnt, const vector<int> &need) { 168 int res = 0; 169 for (int i = 0; i < 3; ++i) { 170 res += abs(cnt[i] - need[i]); 171 } 172 assert(res % 2 == 0); 173 return res / 2; 174 } 175 176 int main() { 177 #ifdef _DEBUG 178 freopen("input.txt", "r", stdin); 179 // freopen("output.txt", "w", stdout); 180 #endif 181 182 string s; 183 cin >> n >> s; 184 185 vector<int> cnt(3), cur(3, n / 3); 186 for (auto c : s) { 187 ++cnt[c - '0']; 188 } 189 190 int need = needRep(cnt, cur); 191 192 int curRep = 0; 193 for (int i = 0; i < n; ++i) { 194 --cnt[s[i] - '0']; 195 for (int j = 0; j < 3; ++j) { 196 if (cur[j] == 0) continue; 197 int rep = j != s[i] - '0'; 198 --cur[j]; 199 if (curRep + rep + needRep(cnt, cur) == need) { 200 s[i] = j + '0'; 201 curRep += rep; 202 break; 203 } 204 ++cur[j]; 205 } 206 } 207 208 cout << s << endl; 209 210 return 0; 211 } 212 ``` 213 214 **Solution (PikMike)** 215 216 ``` 217 n = int(input()) 218 s = [ord(x) - ord('0') for x in input()] 219 cnt = [s.count(x) for x in [0, 1, 2]] 220 def forw(x): 221 for i in range(n): 222 if (cnt[x] < n // 3 and s[i] > x and cnt[s[i]] > n // 3): 223 cnt[x] += 1 224 cnt[s[i]] -= 1 225 s[i] = x 226 def back(x): 227 for i in range(n - 1, -1, -1): 228 if (cnt[x] < n // 3 and s[i] < x and cnt[s[i]] > n // 3): 229 cnt[x] += 1 230 cnt[s[i]] -= 1 231 s[i] = x 232 forw(0) 233 forw(1) 234 back(2) 235 back(1) 236 print(''.join([str(x) for x in s])) 237 ``` 238 239 [1102E - Monotonic Renumeration](/contest/1102/problem/E "Codeforces Round 531 (Div. 3)") 240 241 **Tutorial** 242 243 Tutorial is loading... 244 245 **Solution** 246 247 ``` 248 #include <bits/stdc++.h> 249 250 using namespace std; 251 252 const int MOD = 998244353; 253 254 int main() 255 { 256 int n; 257 scanf("%d", &n); 258 vector<int> a(n); 259 for(int i = 0; i < n; i++) 260 scanf("%d", &a[i]); 261 map<int, int> lst; 262 vector<int> last_pos(n); 263 for(int i = n - 1; i >= 0; i--) 264 { 265 if(!lst.count(a[i])) 266 lst[a[i]] = i; 267 last_pos[i] = lst[a[i]]; 268 } 269 int ans = 1; 270 int cur_max = -1; 271 for(int i = 0; i < n - 1; i++) 272 { 273 cur_max = max(cur_max, last_pos[i]); 274 if(cur_max == i) 275 ans = (2 * ans) % MOD; 276 } 277 printf("%d\n", ans); 278 return 0; 279 } 280 ``` 281 282 [1102F - Elongated Matrix](/contest/1102/problem/F "Codeforces Round 531 (Div. 3)") 283 284 **Tutorial** 285 286 Tutorial is loading... 287 288 **Solution 1** 289 290 ``` 291 #include <bits/stdc++.h> 292 293 #define forn(i, n) for (int i = 0; i < int(n); i++) 294 295 using namespace std; 296 297 typedef long long li; 298 299 const int N = 18; 300 const int M = 100 * 1000 + 13; 301 const int INF = 1e9; 302 303 int dp[1 << N][N]; 304 305 int n, m; 306 int a[N][M]; 307 int mn1[N][N], mn2[N][N]; 308 309 int calc(int mask, int v){ 310 if (dp[mask][v] != -1) 311 return dp[mask][v]; 312 dp[mask][v] = 0; 313 forn(u, n) if (v != u && ((mask >> u) & 1)) 314 dp[mask][v] = max(dp[mask][v], min(mn1[u][v], calc(mask ^ (1 << v), u))); 315 return dp[mask][v]; 316 } 317 318 int main() { 319 scanf("%d%d", &n, &m); 320 forn(i, n) forn(j, m) 321 scanf("%d", &a[i][j]); 322 323 forn(i, n) forn(j, n){ 324 int val = INF; 325 forn(k, m) 326 val = min(val, abs(a[i][k] - a[j][k])); 327 mn1[i][j] = val; 328 val = INF; 329 forn(k, m - 1) 330 val = min(val, abs(a[i][k] - a[j][k + 1])); 331 mn2[i][j] = val; 332 } 333 334 int ans = 0; 335 forn(i, n){ 336 memset(dp, -1, sizeof(dp)); 337 forn(j, n) 338 dp[1 << j][j] = (j == i ? INF : 0); 339 forn(j, n) 340 ans = max(ans, min(mn2[j][i], calc((1 << n) - 1, j))); 341 } 342 343 printf("%d\n", ans); 344 } 345 ``` 346 347 **Solution 2** 348 349 ``` 350 #include <bits/stdc++.h> 351 352 #define forn(i, n) for (int i = 0; i < int(n); i++) 353 354 using namespace std; 355 356 const int N = 18; 357 const int M = 100 * 1000 + 13; 358 const int INF = 1e9; 359 360 int used[1 << N]; 361 char dp[1 << N]; 362 int g[1 << N]; 363 364 int n, m; 365 int a[N][M]; 366 int mn1[N][N], mn2[N][N]; 367 368 bool calc(int mask){ 369 if (dp[mask] != -1) 370 return dp[mask]; 371 used[mask] = 0; 372 dp[mask] = 0; 373 forn(i, n){ 374 if (!((mask >> i) & 1)) 375 continue; 376 if (!calc(mask ^ (1 << i))) 377 continue; 378 if (!(used[mask ^ (1 << i)] & g[i])) 379 continue; 380 used[mask] |= (1 << i); 381 dp[mask] = 1; 382 } 383 return dp[mask]; 384 } 385 386 bool check(int k){ 387 forn(i, n){ 388 g[i] = 0; 389 forn(j, n) 390 g[i] |= (1 << j) * (mn1[j][i] >= k); 391 } 392 forn(i, n){ 393 memset(dp, -1, sizeof(dp)); 394 forn(j, n){ 395 dp[1 << j] = (j == i); 396 used[1 << j] = (1 << j); 397 } 398 calc((1 << n) - 1); 399 forn(j, n) if (mn2[j][i] >= k && ((used[(1 << n) - 1] >> j) & 1)) 400 return true; 401 } 402 return false; 403 } 404 405 int main() { 406 scanf("%d%d", &n, &m); 407 forn(i, n) forn(j, m) 408 scanf("%d", &a[i][j]); 409 410 forn(i, n) forn(j, n){ 411 int val = INF; 412 forn(k, m) 413 val = min(val, abs(a[i][k] - a[j][k])); 414 mn1[i][j] = val; 415 val = INF; 416 forn(k, m - 1) 417 val = min(val, abs(a[i][k] - a[j][k + 1])); 418 mn2[i][j] = val; 419 } 420 421 int l = 0, r = INF; 422 while (l < r - 1){ 423 int m = (l + r) / 2; 424 if (check(m)) 425 l = m; 426 else 427 r = m; 428 } 429 430 printf("%d\n", check(r) ? r : l); 431 } 432 ```