1398.md (10095B)
1 Source: https://codeforces.com/blog/entry/81506 2 3 [1398A - Bad Triangle](/contest/1398/problem/A "Educational Codeforces Round 93 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 a = list(map(int, input().split())) 17 if a[0] + a[1] > a[-1]: 18 print(-1) 19 else: 20 print(1, 2, n) 21 ``` 22 23 [1398B - Substring Removal Game](/contest/1398/problem/B "Educational Codeforces Round 93 (Rated for Div. 2)") 24 25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (Ne0n25)** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 using namespace std; 37 38 #define sz(a) int((a).size()) 39 #define forn(i, n) for (int i = 0; i < int(n); ++i) 40 41 void solve() { 42 string s; 43 cin >> s; 44 vector<int> a; 45 forn(i, sz(s)) if (s[i] == '1') { 46 int j = i; 47 while (j + 1 < sz(s) && s[j + 1] == '1') 48 ++j; 49 a.push_back(j - i + 1); 50 i = j; 51 } 52 sort(a.rbegin(), a.rend()); 53 int ans = 0; 54 for (int i = 0; i < sz(a); i += 2) 55 ans += a[i]; 56 cout << ans << endl; 57 } 58 59 int main() { 60 int T; 61 cin >> T; 62 while (T--) solve(); 63 } 64 ``` 65 66 [1398C - Good Subarrays](/contest/1398/problem/C "Educational Codeforces Round 93 (Rated for Div. 2)") 67 68 Idea: [Roms](/profile/Roms "Master Roms") 69 70 **Tutorial** 71 72 Tutorial is loading... 73 74 **Solution (Roms)** 75 76 ``` 77 for _ in range(int(input())): 78 n = int(input()) 79 a = input() 80 d = {0 : 1} 81 res, s = 0, 0 82 83 for i in range(n): 84 s += int(a[i]) 85 x = s - i - 1 86 if x not in d: 87 d[x] = 0 88 d[x] += 1 89 res += d[x] - 1 90 91 print(res) 92 ``` 93 94 [1398D - Colored Rectangles](/contest/1398/problem/D "Educational Codeforces Round 93 (Rated for Div. 2)") 95 96 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution (pikmike)** 103 104 ``` 105 n = [int(x) for x in input().split()] 106 a = [] 107 for i in range(3): 108 a.append([int(x) for x in input().split()]) 109 a[i].sort(reverse=True) 110 111 dp = [[[0 for i in range(n[2] + 1)] for j in range(n[1] + 1)] for k in range(n[0] + 1)] 112 ans = 0 113 for i in range(n[0] + 1): 114 for j in range(n[1] + 1): 115 for k in range(n[2] + 1): 116 if i < n[0] and j < n[1]: 117 dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + a[0][i] * a[1][j]) 118 if i < n[0] and k < n[2]: 119 dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + a[0][i] * a[2][k]) 120 if j < n[1] and k < n[2]: 121 dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + a[1][j] * a[2][k]) 122 ans = max(ans, dp[i][j][k]) 123 124 print(ans) 125 ``` 126 127 [1398E - Two Types of Spells](/contest/1398/problem/E "Educational Codeforces Round 93 (Rated for Div. 2)") 128 129 Idea: [Roms](/profile/Roms "Master Roms") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 130 131 **Tutorial** 132 133 Tutorial is loading... 134 135 **Solution (Roms)** 136 137 ``` 138 #include <bits/stdc++.h> 139 140 using namespace std; 141 142 const int N = int(1e5) + 9; 143 144 int n; 145 set <int> sDouble; 146 long long sum[2]; 147 set <int> s[2]; 148 int cntDouble[2]; 149 150 // 0: 0 -> 1 151 // 1: 1 -> 0 152 void upd(int id) { 153 assert(s[id].size() > 0); 154 int x = *s[id].rbegin(); 155 if (id == 1) x = *s[id].begin(); 156 bool d = sDouble.count(x); 157 158 sum[id] -= x, sum[!id] += x; 159 s[id].erase(x), s[!id].insert(x); 160 cntDouble[id] -= d, cntDouble[!id] += d; 161 } 162 163 int main(){ 164 cin >> n; 165 for (int i = 0; i < n; ++i) { 166 int tp, x; 167 cin >> tp >> x;// tp = 1 if double 168 169 if (x > 0) { 170 sum[0] += x; 171 s[0].insert(x); 172 cntDouble[0] += tp; 173 if (tp) sDouble.insert(x); 174 } else { 175 x = -x; 176 int id = 0; 177 if (s[1].count(x)) id = 1; 178 else assert(s[0].count(x)); 179 180 sum[id] -= x; 181 s[id].erase(x); 182 cntDouble[id] -= tp; 183 if (tp) { 184 assert(sDouble.count(x)); 185 sDouble.erase(x); 186 } 187 } 188 189 int sumDouble = cntDouble[0] + cntDouble[1]; 190 while (s[1].size() < sumDouble) upd(0); 191 while (s[1].size() > sumDouble) upd(1); 192 while (s[1].size() > 0 && s[0].size() > 0 && *s[0].rbegin() > *s[1].begin()) { 193 upd(0); 194 upd(1); 195 } 196 assert(s[1].size() == sumDouble); 197 198 long long res = sum[0] + sum[1] * 2; 199 if (cntDouble[1] == sumDouble && sumDouble > 0) { 200 res -= *s[1].begin(); 201 if (s[0].size() > 0) res += *s[0].rbegin(); 202 } 203 cout << res << endl; 204 } 205 return 0; 206 } 207 ``` 208 209 [1398F - Controversial Rounds](/contest/1398/problem/F "Educational Codeforces Round 93 (Rated for Div. 2)") 210 211 Idea: [Roms](/profile/Roms "Master Roms") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution (Roms)** 218 219 ``` 220 #include <bits/stdc++.h> 221 222 using namespace std; 223 224 const int N = int(1e6) + 99; 225 const int INF = int(1e9) + 99; 226 227 int n; 228 string s; 229 vector <int> p[2][N]; 230 int nxt[2][N]; 231 int ptr[2]; 232 char buf[N]; 233 234 int main(){ 235 cin >> n >> s; 236 237 for (int i = n - 1; i >= 0; --i) { 238 if (s[i] != '0') nxt[0][i] = 1 + nxt[0][i + 1]; 239 if (s[i] != '1') nxt[1][i] = 1 + nxt[1][i + 1]; 240 } 241 242 for (int b = 0; b <= 1; ++b) { 243 int l = 0; 244 while (l < n) { 245 if (s[l] == char('0' + b)) { 246 ++l; 247 continue; 248 } 249 int r = l + 1; 250 while (r < n && s[r] != char('0' + b)) ++r; 251 for (int len = 1; len <= r - l; ++len) 252 p[b][len].push_back(l); 253 l = r; 254 } 255 } 256 257 for (int len = 1; len <= n; ++len) { 258 int pos = 0, res = 0; 259 ptr[0] = ptr[1] = 0; 260 261 while (pos < n) { 262 int npos = INF; 263 for (int b = 0; b <= 1; ++b) { 264 if (nxt[b][pos] >= len) 265 npos = min(npos, pos + len); 266 while (ptr[b] < p[b][len].size() && pos > p[b][len][ ptr[b] ]) 267 ++ptr[b]; 268 if (ptr[b] < p[b][len].size()) 269 npos = min(npos, p[b][len][ ptr[b] ] + len); 270 } 271 if (npos != INF) 272 ++res; 273 pos = npos; 274 } 275 276 cout << res << ' '; 277 } 278 cout << endl; 279 280 return 0; 281 } 282 ``` 283 284 [1398G - Running Competition](/contest/1398/problem/G "Educational Codeforces Round 93 (Rated for Div. 2)") 285 286 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 287 288 **Tutorial** 289 290 Tutorial is loading... 291 292 **Solution (BledDest)** 293 294 ``` 295 #include<bits/stdc++.h> 296 297 using namespace std; 298 299 #define forn(i, n) for(int i = 0; i < n; i++) 300 #define sz(a) ((int)(a).size()) 301 302 const int LOGN = 20; 303 const int N = (1 << LOGN); 304 const int K = 200043; 305 const int M = 1000043; 306 307 typedef double ld; 308 typedef long long li; 309 310 const ld PI = acos(-1.0); 311 312 struct comp 313 { 314 ld x, y; 315 comp(ld x = .0, ld y = .0) : x(x), y(y) {} 316 inline comp conj() { return comp(x, -y); } 317 }; 318 319 inline comp operator +(const comp &a, const comp &b) 320 { 321 return comp(a.x + b.x, a.y + b.y); 322 } 323 324 inline comp operator -(const comp &a, const comp &b) 325 { 326 return comp(a.x - b.x, a.y - b.y); 327 } 328 329 inline comp operator *(const comp &a, const comp &b) 330 { 331 return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); 332 } 333 334 inline comp operator /(const comp &a, const ld &b) 335 { 336 return comp(a.x / b, a.y / b); 337 } 338 339 vector<comp> w[LOGN]; 340 vector<int> rv[LOGN]; 341 342 void precalc() 343 { 344 for(int st = 0; st < LOGN; st++) 345 { 346 w[st].assign(1 << st, comp()); 347 for(int k = 0; k < (1 << st); k++) 348 { 349 double ang = PI / (1 << st) * k; 350 w[st][k] = comp(cos(ang), sin(ang)); 351 } 352 353 rv[st].assign(1 << st, 0); 354 if(st == 0) 355 { 356 rv[st][0] = 0; 357 continue; 358 } 359 int h = (1 << (st - 1)); 360 for(int k = 0; k < (1 << st); k++) 361 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 362 } 363 } 364 365 inline void fft(comp a[N], int n, int ln, bool inv) 366 { 367 for(int i = 0; i < n; i++) 368 { 369 int ni = rv[ln][i]; 370 if(i < ni) 371 swap(a[i], a[ni]); 372 } 373 374 for(int st = 0; (1 << st) < n; st++) 375 { 376 int len = (1 << st); 377 for(int k = 0; k < n; k += (len << 1)) 378 { 379 for(int pos = k; pos < k + len; pos++) 380 { 381 comp l = a[pos]; 382 comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]); 383 384 a[pos] = l + r; 385 a[pos + len] = l - r; 386 } 387 } 388 } 389 390 if(inv) for(int i = 0; i < n; i++) 391 a[i] = a[i] / n; 392 } 393 394 comp aa[N]; 395 comp bb[N]; 396 comp cc[N]; 397 398 inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc) 399 { 400 int n = 1, ln = 0; 401 while(n < (sza + szb)) 402 n <<= 1, ln++; 403 for(int i = 0; i < n; i++) 404 aa[i] = (i < sza ? a[i] : comp()); 405 for(int i = 0; i < n; i++) 406 bb[i] = (i < szb ? b[i] : comp()); 407 408 fft(aa, n, ln, false); 409 fft(bb, n, ln, false); 410 411 for(int i = 0; i < n; i++) 412 cc[i] = aa[i] * bb[i]; 413 414 fft(cc, n, ln, true); 415 416 szc = n; 417 for(int i = 0; i < n; i++) 418 c[i] = cc[i]; 419 } 420 421 comp a[N]; 422 comp b[N]; 423 comp c[N]; 424 int used[M]; 425 int dp[M]; 426 427 int main() 428 { 429 precalc(); 430 int n, x, y; 431 for(int i = 0; i < M; i++) 432 dp[i] = -1; 433 scanf("%d %d %d", &n, &x, &y); 434 vector<int> A(n + 1); 435 for(int i = 0; i <= n; i++) 436 scanf("%d", &A[i]); 437 for(int i = 0; i <= n; i++) 438 { 439 a[A[i]] = comp(1.0, 0.0); 440 b[K - A[i]] = comp(1.0, 0.0); 441 } 442 int s = 0; 443 multiply(a, K + 1, b, K + 1, c, s); 444 for(int i = K + 1; i < s; i++) 445 if(c[i].x > 0.5) 446 used[(i - K + y) * 2] = 1; 447 for(int i = 1; i < M; i++) 448 { 449 if(!used[i]) continue; 450 for(int j = i; j < M; j += i) 451 dp[j] = max(dp[j], i); 452 } 453 int q; 454 scanf("%d", &q); 455 for(int i = 0; i < q; i++) 456 { 457 int l; 458 scanf("%d", &l); 459 printf("%d ", dp[l]); 460 } 461 } 462 ```