1692.md (9223B)
1 Source: https://codeforces.com/blog/entry/103883 2 3 Thanks for participating! 4 5 [1692A - Marathon](/contest/1692/problem/A "Codeforces Round 799 (Div. 4)") 6 7 Idea: [mesanu](/profile/mesanu "Expert mesanu") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 t = int(input()) 17 for test in range(t): 18 a,b,c,d = map(int, input().split()) 19 rs = (b > a) + (c > a) + (d > a) 20 print(rs) 21 ``` 22 23 [1692B - All Distinct](/contest/1692/problem/B "Codeforces Round 799 (Div. 4)") 24 25 Idea: [mesanu](/profile/mesanu "Expert mesanu") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution** 32 33 ``` 34 #include <bits/stdc++.h> 35 typedef long long ll; 36 using namespace std; 37 38 void solve() 39 { 40 int n, x; 41 cin >> n; 42 set<int> a; 43 for(int i = 0; i < n; i++) 44 { 45 cin >> x; 46 a.insert(x); 47 } 48 if((n-a.size())%2 == 0) 49 { 50 cout << a.size() << endl; 51 } 52 else 53 { 54 cout << a.size()-1 << endl; 55 } 56 } 57 58 int32_t main(){ 59 int t = 1; 60 cin >> t; 61 while (t--) { 62 solve(); 63 } 64 } 65 ``` 66 67 [1692C - Where's the Bishop?](/contest/1692/problem/C "Codeforces Round 799 (Div. 4)") 68 69 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 **Solution** 76 77 ``` 78 #include <bits/stdc++.h> 79 80 using namespace std; 81 82 void solve() { 83 char g[9][9]; 84 for (int i = 1; i <= 8; i++) { 85 for (int j = 1; j <= 8; j++) { 86 cin >> g[i][j]; 87 } 88 } 89 for (int i = 2; i <= 7; i++) { 90 for (int j = 2; j <= 7; j++) { 91 if (g[i][j] == '#' && g[i - 1][j - 1] == '#' && g[i - 1][j + 1] == '#' && g[i + 1][j - 1] == '#' && g[i + 1][j + 1] == '#') { 92 cout << i << ' ' << j << '\n'; return; 93 } 94 } 95 } 96 } 97 98 int main() { 99 ios::sync_with_stdio(false); 100 cin.tie(nullptr); 101 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 102 // solve(); 103 } 104 ``` 105 106 [1692D - The Clock](/contest/1692/problem/D "Codeforces Round 799 (Div. 4)") 107 108 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG") 109 110 **Tutorial** 111 112 Tutorial is loading... 113 114 **Solution** 115 116 ``` 117 #include <bits/stdc++.h> 118 119 using namespace std; 120 121 int a[5] = {600, 60, 0, 10, 1}; 122 int good[16] = {0, 70, 140, 210, 280, 350, 601, 671, 741, 811, 881, 951, 1202, 1272, 1342, 1412}; 123 124 void solve() { 125 string s; 126 cin >> s; 127 int x; 128 cin >> x; 129 int tot = 0; 130 for (int i = 0; i < 5; i++) { 131 tot += (int)(s[i] - '0') * a[i]; 132 } 133 set<int> t; 134 for (int i = 0; i < 2022; i++) { 135 t.insert(tot); 136 tot += x; 137 tot %= 1440; 138 } 139 int res = 0; 140 for (int i : t) { 141 for (int j = 0; j < 16; j++) { 142 if (good[j] == i) {res++;} 143 } 144 } 145 cout << res << '\n'; 146 } 147 148 int main() { 149 ios::sync_with_stdio(false); 150 cin.tie(nullptr); 151 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 152 // solve(); 153 } 154 ``` 155 156 [1692E - Binary Deque](/contest/1692/problem/E "Codeforces Round 799 (Div. 4)") 157 158 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 159 160 **Tutorial** 161 162 Tutorial is loading... 163 164 **Solution** 165 166 ``` 167 #include "bits/stdc++.h" 168 using namespace std; 169 170 #define ll long long 171 172 #define forn(i,n) for(int i=0;i<n;i++) 173 #define all(v) v.begin(), v.end() 174 #define rall(v) v.rbegin(),v.rend() 175 176 #define pb push_back 177 #define sz(a) (int)a.size() 178 179 ll query(int l, int r, vector<ll>& p) { 180 return p[r] - (l ? p[l - 1] : 0); 181 } 182 183 void solve() { 184 int n, s; cin >> n >> s; 185 vector<ll> a(n), p(n); 186 forn(i, n) { 187 cin >> a[i]; 188 p[i] = a[i]; 189 if(i) p[i] += p[i - 1]; 190 } 191 192 int ans = INT_MAX; 193 194 for(int i = 0; i < n; ++i) { 195 int l = i, r = n - 1, pos = -1; 196 while(l <= r) { 197 int mid = l + r >> 1; 198 if(query(i, mid, p) <= s) { 199 pos = mid; 200 l = mid + 1; 201 } else r = mid - 1; 202 } 203 if(pos == -1 || query(i, pos, p) != s) continue; 204 ans = min(ans, n - (pos - i + 1)); 205 } 206 207 cout << (ans == INT_MAX ? -1 : ans) << "\n"; 208 } 209 210 int32_t main() { 211 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 212 int t = 1; 213 cin >> t; 214 while(t--) { 215 solve(); 216 } 217 } 218 ``` 219 220 [1692F - 3SUM](/contest/1692/problem/F "Codeforces Round 799 (Div. 4)") 221 222 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 223 224 **Tutorial** 225 226 Tutorial is loading... 227 228 **Solution** 229 230 ``` 231 #include <bits/stdc++.h> 232 233 using namespace std; 234 235 void solve() { 236 int n; 237 cin >> n; 238 int cnt[10] = {}; 239 for (int i = 0; i < n; i++) { 240 int x; 241 cin >> x; 242 cnt[x % 10]++; 243 } 244 vector<int> v; 245 for (int i = 0; i < 10; i++) { 246 for (int j = 0; j < min(cnt[i], 3); j++) { 247 v.push_back(i); 248 } 249 } 250 int m = v.size(); 251 for (int i = 0; i < m; i++) { 252 for (int j = i + 1; j < m; j++) { 253 for (int k = j + 1; k < m; k++) { 254 if ((v[i] + v[j] + v[k]) % 10 == 3) {cout << "YES\n"; return;} 255 } 256 } 257 } 258 cout << "NO\n"; 259 } 260 261 int main() { 262 ios::sync_with_stdio(false); 263 cin.tie(nullptr); 264 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 265 // solve(); 266 } 267 ``` 268 269 [1692G - 2^Sort](/contest/1692/problem/G "Codeforces Round 799 (Div. 4)") 270 271 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 272 273 **Tutorial** 274 275 Tutorial is loading... 276 277 **Solution** 278 279 ``` 280 #include <bits/stdc++.h> 281 282 using namespace std; 283 284 const int MAX = 200007; 285 const int MOD = 1000000007; 286 287 void solve() { 288 int n, k; 289 cin >> n >> k; 290 int a[n]; 291 for (int i = 0; i < n; i++) { 292 cin >> a[i]; 293 } 294 int ok[n]; 295 for (int i = 0; i < n - 1; i++) { 296 ok[i] = (a[i] < 2 * a[i + 1]); 297 } 298 int tot = 0; 299 for (int i = 0; i < k; i++) { 300 tot += ok[i]; 301 } 302 int res = 0; 303 if (tot == k) {res++;} 304 for (int i = k; i < n - 1; i++) { 305 tot += ok[i]; 306 tot -= ok[i - k]; 307 if (tot == k) {res++;} 308 } 309 cout << res << '\n'; 310 } 311 312 int main() { 313 ios::sync_with_stdio(false); 314 cin.tie(nullptr); 315 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 316 // solve(); 317 } 318 ``` 319 320 [1692H - Gambling](/contest/1692/problem/H "Codeforces Round 799 (Div. 4)") 321 322 Idea: [mesanu](/profile/mesanu "Expert mesanu") 323 324 **Tutorial** 325 326 Tutorial is loading... 327 328 **Solution** 329 330 ``` 331 #include "bits/stdc++.h" 332 using namespace std; 333 334 #define ll long long 335 336 #define forn(i,n) for(int i=0;i<n;i++) 337 #define all(v) v.begin(), v.end() 338 #define rall(v) v.rbegin(),v.rend() 339 340 #define pb push_back 341 #define sz(a) (int)a.size() 342 343 struct DynamicMaxSubarraySum { 344 struct node { 345 ll pref, suf, val, sum; 346 }; 347 int N; 348 ll neutral; 349 vector<node> t; 350 DynamicMaxSubarraySum(int _N, ll assign_value) { 351 neutral = assign_value; 352 N = _N; 353 t.resize(4 * N); 354 forn(i, 4 * N) t[i] = {0, 0, 0, 0}; 355 build(1, 0, N - 1); 356 } 357 void build(int i, int l, int r) { 358 if(l == r) { 359 t[i].pref = t[i].suf = t[i].val = t[i].sum = neutral; 360 return; 361 } 362 int mid = (l + r) >> 1; 363 build(2 * i, l, mid); 364 build(2 * i + 1, mid + 1, r); 365 t[i] = merge(t[2 * i], t[2 * i + 1]); 366 } 367 node merge(node a, node b) { 368 node c; 369 c.pref = max(a.pref, a.sum + b.pref); 370 c.suf = max(b.suf, b.sum + a.suf); 371 c.val = max({a.val, b.val, a.suf + b.pref}); 372 c.sum = a.sum + b.sum; 373 return c; 374 } 375 376 void modif(int i, int l, int r, int pos, ll val) { 377 if(l > pos || r < pos) return; 378 if(l == pos && r == pos) { 379 t[i].pref = t[i].suf = t[i].val = t[i].sum = val; 380 return; 381 } 382 int mid = (l + r) >> 1; 383 modif(2 * i, l, mid, pos, val); 384 modif(2 * i + 1, mid + 1, r, pos, val); 385 t[i] = merge(t[2 * i], t[2 * i + 1]); 386 } 387 node query(int i, int l, int r, int tl, int tr) { 388 if(l > tr || r < tl) return {0, 0, 0, 0}; 389 if(l >= tl && r <= tr) return t[i]; 390 int mid = (l + r) >> 1; 391 return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr)); 392 } 393 394 void modif(int pos, int val) { 395 modif(1, 0, N - 1, pos, val); 396 } 397 node query(int l, int r) { 398 return query(1, 0, N - 1, l, r); 399 } 400 node query(int pos) { 401 return query(1, 0, N - 1, pos, pos); 402 } 403 }; 404 405 void solve() { 406 int n; cin >> n; 407 vector<int> a(n); 408 forn(i, n) cin >> a[i]; 409 map<int, vector<int>> vv; 410 forn(i, n) { 411 vv[a[i]].pb(i); 412 } 413 DynamicMaxSubarraySum st(n, -1); 414 415 ll mx = 0, ans = -1; 416 for(auto i: vv) { 417 vector<int> v = i.second; 418 for(auto x: v) st.modif(x, 1); 419 if(mx < st.query(0, n - 1).val) { 420 ans = i.first; 421 mx = st.query(0, n - 1).val; 422 } 423 for(auto x: v) st.modif(x, -1); 424 } 425 int ansl = -1, ansr = -1; 426 for(int i = 0; i < n; ++i) { 427 if(a[i] == ans) a[i] = 1; 428 else a[i] = -1; 429 } 430 ll sum = 0, lastl = 0; 431 mx = 0; 432 for(int i = 0; i < n; ++i) { 433 sum += a[i]; 434 if(sum > mx) { 435 mx = sum; 436 ansr = i; 437 ansl = lastl; 438 } 439 if(sum <= 0) { 440 lastl = i + 1; 441 sum = 0; 442 } 443 } 444 445 cout << ans << " " << ansl + 1 << " " << ansr + 1 << "\n"; 446 } 447 448 int32_t main() { 449 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 450 int t = 1; 451 cin >> t; 452 while(t--) { 453 solve(); 454 } 455 } 456 ```