1117.md (9833B)
1 Source: https://codeforces.com/blog/entry/65365 2 3 [1117A - Best Subsegment](/contest/1117/problem/A "Educational Codeforces Round 60 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (adedalic)** 10 11 ``` 12 #include<iostream> 13 using namespace std; 14 15 int main() { 16 int n; cin >> n; 17 int mx = -1, lenMx = 0; 18 19 int curEl = -1, curLen = 0; 20 for(int i = 0; i < n; i++) { 21 int a; cin >> a; 22 23 if(curEl != a) 24 curEl = a, curLen = 0; 25 curLen++; 26 27 if(mx < curEl) 28 mx = curEl, lenMx = 0; 29 if(mx == curEl) 30 lenMx = max(lenMx, curLen); 31 } 32 cout << lenMx << endl; 33 return 0; 34 } 35 ``` 36 37 [1117B - Emotes](/contest/1117/problem/B "Educational Codeforces Round 60 (Rated for Div. 2)") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (Vovuh)** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 int main() { 51 #ifdef _DEBUG 52 freopen("input.txt", "r", stdin); 53 // freopen("output.txt", "w", stdout); 54 #endif 55 56 int n, m, k; 57 cin >> n >> m >> k; 58 59 vector<int> a(n); 60 for (int i = 0; i < n; ++i) { 61 cin >> a[i]; 62 } 63 sort(a.rbegin(), a.rend()); 64 65 cout << m / (k + 1) * 1ll * (a[0] * 1ll * k + a[1]) + m % (k + 1) * 1ll * a[0] << endl; 66 67 return 0; 68 } 69 ``` 70 71 [1117C - Magic Ship](/contest/1117/problem/C "Educational Codeforces Round 60 (Rated for Div. 2)") 72 73 **Tutorial** 74 75 Tutorial is loading... 76 77 **Solution (Roms)** 78 79 ``` 80 #include <bits/stdc++.h> 81 82 using namespace std; 83 84 #define x first 85 #define y second 86 87 const int N = 100009; 88 89 pair<int, int> st, fi; 90 int n; 91 string s; 92 93 string mv = "UDLR"; 94 int dx[] = {0, 0, -1, 1}; 95 int dy[] = {1, -1, 0, 0}; 96 97 pair<int, int> d[N]; 98 99 int main(){ 100 cin >> st.x >> st.y >> fi.x >> fi.y; 101 cin >> n >> s; 102 103 for(int i = 0; i < n; ++i){ 104 int id = -1; 105 for(int j = 0; j < 4; ++j) 106 if(mv[j] == s[i]) 107 id = j; 108 assert(id != -1); 109 d[i + 1] = make_pair(d[i].x + dx[id], d[i].y + dy[id]); 110 } 111 112 long long l = 0, r = 1e18; 113 while(r - l > 1){ 114 long long mid = (l + r) / 2; 115 long long cnt = mid / n, rem = mid % n; 116 long long x = st.x + d[rem].x + cnt * 1LL * d[n].x; 117 long long y = st.y + d[rem].y + cnt * 1LL * d[n].y; 118 long long dist = abs(x - fi.x) + abs(y - fi.y); 119 if(dist <= mid) 120 r = mid; 121 else 122 l = mid; 123 } 124 125 if(r > 5e17) r = -1; 126 cout << r << endl; 127 128 return 0; 129 } 130 ``` 131 132 [1117D - Magic Gems](/contest/1117/problem/D "Educational Codeforces Round 60 (Rated for Div. 2)") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution (Reziba)** 139 140 ``` 141 #include<bits/stdc++.h> 142 #define pb push_back 143 #define mp make_pair 144 #define fi first 145 #define se second 146 #define MOD 1000000007 147 #define MOD9 1000000009 148 #define pi 3.1415926535 149 #define ms(s, n) memset(s, n, sizeof(s)) 150 #define prec(n) fixed<<setprecision(n) 151 #define eps 0.000001 152 #define all(v) v.begin(), v.end() 153 #define allr(v) v.rbegin(), v.rend() 154 #define bolt ios::sync_with_stdio(0) 155 #define light cin.tie(0);cout.tie(0) 156 #define forr(i,p,n) for(ll i=p;i<n;i++) 157 #define MAXN 1000003 158 typedef long long ll; 159 using namespace std; 160 ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;} 161 ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;} 162 ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;} 163 ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);} 164 ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;} 165 166 ll bin[103][103]; 167 168 void mult_mat(ll m, ll ans[][100], ll bin[][100]){ 169 ll mult[m][m]; 170 forr(i,0,m){ 171 forr(j,0,m){ 172 mult[i][j]=0; 173 forr(k,0,m){ 174 mult[i][j]+=ans[i][k]*bin[k][j]; 175 if(mult[i][j]>=MOD){ 176 mult[i][j]%=MOD; 177 } 178 } 179 } 180 } 181 forr(i,0,m){ 182 forr(j,0,m){ 183 ans[i][j]=mult[i][j]; 184 } 185 } 186 } 187 188 void pow_mat(ll n, ll fin[][100], ll m){ 189 ll ans[m][100]; 190 ll b[m][100]; 191 forr(i,0,m){ 192 forr(j,0,m){ 193 ans[i][j]=bin[i][j]; 194 b[i][j]=bin[i][j]; 195 } 196 } 197 n--; 198 while(n>0){ 199 if(n%2==1){ 200 mult_mat(m,ans,b); 201 n--; 202 }else{ 203 n=n/2; 204 mult_mat(m,b,b); 205 } 206 } 207 forr(i,0,m){ 208 forr(j,0,m){ 209 fin[i][j]=ans[i][j]; 210 } 211 } 212 } 213 214 int main(){ 215 bolt; 216 ll n,m; 217 cin>>n>>m; 218 bin[0][0]=1; 219 bin[0][m-1]=1; 220 for(ll i=1;i<m;i++){ 221 bin[i][i-1]=1; 222 } 223 if(n<m){ 224 cout<<1<<"\n"; 225 }else{ 226 ll fin[m+1][100]; 227 pow_mat(n-m+1,fin,m); 228 ll ans=0; 229 forr(i,0,m){ 230 ans+=fin[0][i]; 231 if(ans>=MOD){ 232 ans-=MOD; 233 } 234 } 235 cout<<ans<<"\n"; 236 } 237 } 238 ``` 239 240 [1117E - Decypher the String](/contest/1117/problem/E "Educational Codeforces Round 60 (Rated for Div. 2)") 241 242 **Tutorial** 243 244 Tutorial is loading... 245 246 **Solution (BledDest)** 247 248 ``` 249 #include <bits/stdc++.h> 250 251 using namespace std; 252 253 int main() 254 { 255 string t; 256 cin >> t; 257 int n = t.size(); 258 string s1(n, 'a'), s2(n, 'a'), s3(n, 'a'); 259 for(int i = 0; i < n; i++) 260 { 261 s1[i] = char('a' + (i % 26)); 262 s2[i] = char('a' + ((i / 26) % 26)); 263 s3[i] = char('a' + ((i / 26 / 26) % 26)); 264 } 265 cout << "? " << s1 << endl; 266 string t1; 267 cin >> t1; 268 cout << "? " << s2 << endl; 269 string t2; 270 cin >> t2; 271 cout << "? " << s3 << endl; 272 string t3; 273 cin >> t3; 274 vector<int> p(n); 275 for(int i = 0; i < n; i++) 276 p[i] = (t1[i] - 'a') + (t2[i] - 'a') * 26 + (t3[i] - 'a') * 26 * 26; 277 string s(n, 'a'); 278 for(int i = 0; i < n; i++) 279 s[p[i]] = t[i]; 280 cout << "! " << s << endl; 281 return 0; 282 } 283 ``` 284 285 [1117F - Crisp String](/contest/1117/problem/F "Educational Codeforces Round 60 (Rated for Div. 2)") 286 287 **Tutorial** 288 289 Tutorial is loading... 290 291 **Solution (PikMike)** 292 293 ``` 294 #include <bits/stdc++.h> 295 296 #define forn(i, n) for (int i = 0; i < int(n); i++) 297 298 using namespace std; 299 300 const int N = 100 * 1000 + 13; 301 const int P = 17; 302 303 int n, p; 304 string s; 305 int A[P][P]; 306 vector<int> pos[P]; 307 int pr[P][N]; 308 bitset<(1 << P)> legal, cur, dp; 309 int cnt[P]; 310 311 int main() { 312 scanf("%d%d", &n, &p); 313 char buf[N]; 314 scanf("%s", buf); 315 s = buf; 316 forn(i, p) forn(j, p) 317 scanf("%d", &A[i][j]); 318 319 forn(i, n){ 320 pos[s[i] - 'a'].push_back(i); 321 forn(j, p) 322 pr[j][i + 1] = pr[j][i] + (s[i] == 'a' + j); 323 } 324 325 legal.reset(); 326 legal.flip(); 327 328 int fl = (1 << p) - 1; 329 forn(c, p) forn(d, c + 1){ 330 if (A[c][d]) continue; 331 cur.reset(); 332 cur.flip(); 333 int i = 0, j = 0; 334 while (i < pos[c].size() && j < pos[d].size()){ 335 if (c == d && i == j){ 336 ++j; 337 continue; 338 } 339 int mask = 0; 340 if (pos[c][i] < pos[d][j]){ 341 forn(e, p) if ((pr[e][pos[d][j]] - pr[e][pos[c][i] + 1]) != 0) 342 mask |= (1 << e); 343 ++i; 344 } 345 else{ 346 forn(e, p) if ((pr[e][pos[c][i]] - pr[e][pos[d][j] + 1]) != 0) 347 mask |= (1 << e); 348 ++j; 349 } 350 if ((mask >> c) & 1) continue; 351 if ((mask >> d) & 1) continue; 352 cur[mask ^ fl] = 0; 353 } 354 for (int mask = fl; mask > 0; --mask){ 355 if (cur[mask]) continue; 356 forn(e, p) if (c != e && d != e && ((mask >> e) & 1)) 357 cur[mask ^ (1 << e)] = 0; 358 } 359 legal &= cur; 360 } 361 362 dp[fl] = 1; 363 for (int mask = fl; mask > 0; --mask){ 364 if (!dp[mask]) continue; 365 forn(i, p) if ((mask >> i) & 1){ 366 int nmask = mask ^ (1 << i); 367 if (dp[nmask]) continue; 368 dp[nmask] = legal[nmask]; 369 } 370 } 371 372 forn(i, n) 373 ++cnt[s[i] - 'a']; 374 375 int ans = n; 376 forn(mask, 1 << p) if (dp[mask]){ 377 int cur = 0; 378 forn(i, p) if ((mask >> i) & 1) 379 cur += cnt[i]; 380 ans = min(ans, cur); 381 } 382 383 printf("%d\n", ans); 384 385 return 0; 386 } 387 ``` 388 389 [1117G - Recursive Queries](/contest/1117/problem/G "Educational Codeforces Round 60 (Rated for Div. 2)") 390 391 **Tutorial** 392 393 Tutorial is loading... 394 395 **Solution (adedalic)** 396 397 ``` 398 #include<bits/stdc++.h> 399 using namespace std; 400 401 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 402 #define sz(a) int((a).size()) 403 404 #define x first 405 #define y second 406 407 typedef long long li; 408 typedef pair<int, int> pt; 409 410 int n, q; 411 vector<int> a; 412 vector< pair<pt, int> > qs; 413 414 inline bool read() { 415 if(!(cin >> n >> q)) 416 return false; 417 a.resize(n); 418 qs.resize(q); 419 420 fore(i, 0, n) 421 cin >> a[i]; 422 fore(i, 0, q) { 423 cin >> qs[i].x.x; 424 qs[i].x.x--; 425 } 426 fore(i, 0, q) { 427 cin >> qs[i].x.y; 428 qs[i].x.y--; 429 qs[i].y = i; 430 } 431 return true; 432 } 433 434 bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) { 435 if(a.x.y != b.x.y) 436 return a.x.y < b.x.y; 437 if(a.x.x != b.x.x) 438 return a.x.x < b.x.x; 439 return a.y < b.y; 440 } 441 442 typedef pair<li, li> func; 443 func operator +=(func &a, const func &b) { 444 a.x += b.x, a.y += b.y; 445 return a; 446 } 447 448 vector<func> t; 449 void add(int l, int r, const func &f) { 450 for(l += n, r += n; l < r; l >>= 1, r >>= 1) { 451 if(l & 1) t[l++] += f; 452 if(r & 1) t[--r] += f; 453 } 454 } 455 func sum(int pos) { 456 func ans(0, 0); 457 for(pos += n; pos > 0; pos >>= 1) 458 ans += t[pos]; 459 return ans; 460 } 461 462 inline void solve() { 463 vector<li> ans(q, 0); 464 fore(i, 0, q) 465 ans[i] = qs[i].x.y - qs[i].x.x + 1; 466 fore(_, 0, 2) { 467 vector<int> st; 468 vector<int> lf(n, -1); 469 fore(i, 0, n) { 470 while(!st.empty() && a[st.back()] < a[i]) 471 st.pop_back(); 472 if(!st.empty()) 473 lf[i] = st.back(); 474 st.push_back(i); 475 } 476 477 sort(qs.begin(), qs.end(), cmp); 478 t.assign(2 * n, {0, 0}); 479 480 int uk = 0; 481 fore(i, 0, n) { 482 add(0, lf[i] + 1, {0, i - lf[i] - 1}); 483 add(lf[i] + 1, i, {-1, i}); 484 485 while(uk < q && qs[uk].x.y == i) { 486 auto f = sum(qs[uk].x.x); 487 ans[qs[uk].y] += f.x * qs[uk].x.x + f.y; 488 uk++; 489 } 490 } 491 492 reverse(a.begin(), a.end()); 493 for(auto &p : qs) { 494 p.x.x = n - 1 - p.x.x; 495 p.x.y = n - 1 - p.x.y; 496 swap(p.x.x, p.x.y); 497 } 498 } 499 for(auto v : ans) 500 cout << v << ' '; 501 cout << endl; 502 } 503 504 int main() { 505 #ifdef _DEBUG 506 freopen("input.txt", "r", stdin); 507 int tt = clock(); 508 #endif 509 ios_base::sync_with_stdio(false); 510 cin.tie(0), cout.tie(0); 511 cout << fixed << setprecision(15); 512 513 if(read()) { 514 solve(); 515 516 #ifdef _DEBUG 517 cerr << "TIME = " << clock() - tt << endl; 518 tt = clock(); 519 #endif 520 } 521 return 0; 522 } 523 ```