1582.md (7233B)
1 Source: https://codeforces.com/blog/entry/96267 2 3 [1582A - Luntik and Concerts](/contest/1582/problem/A "Codeforces Round 750 (Div. 2)") 4 5 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (74TrAkToR)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 main() { 19 ios_base::sync_with_stdio(0); 20 cin.tie(0); 21 cout.tie(0); 22 int t, a, b, c; 23 cin >> t; 24 while (t--) { 25 cin >> a >> b >> c; 26 cout << (a + c) % 2 << '\n'; 27 } 28 return 0; 29 } 30 ``` 31 32 [1582B - Luntik and Subsequences](/contest/1582/problem/B "Codeforces Round 750 (Div. 2)") 33 34 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (74TrAkToR)** 41 42 ``` 43 #include<bits/stdc++.h> 44 45 using namespace std; 46 47 typedef long long ll; 48 49 int main() { 50 ios_base::sync_with_stdio(0); 51 cin.tie(0); 52 cout.tie(0); 53 int t, n, x; 54 cin >> t; 55 while (t--) { 56 cin >> n; 57 int cnt0 = 0, cnt1 = 0; 58 for (int i = 1; i <= n; ++i) { 59 cin >> x; 60 if (x == 0) cnt0++; 61 if (x == 1) cnt1++; 62 } 63 cout << (1ll << cnt0) * (ll)cnt1 << '\n'; 64 } 65 return 0; 66 } 67 ``` 68 69 [1582C - Grandma Capa Knits a Scarf](/contest/1582/problem/C "Codeforces Round 750 (Div. 2)") 70 71 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 72 73 **Tutorial** 74 75 Tutorial is loading... 76 77 **Solution (74TrAkToR)** 78 79 ``` 80 #include<bits/stdc++.h> 81 82 using namespace std; 83 84 int main() { 85 ios_base::sync_with_stdio(0); 86 cin.tie(0); 87 cout.tie(0); 88 int t, n; 89 cin >> t; 90 while (t--) { 91 string s; 92 cin >> n >> s; 93 int ans = n + 1; 94 for (int c = 0; c < 26; ++c) { 95 int l = 0, r = n - 1, cnt = 0; 96 while (l <= r) { 97 if (s[l] == s[r]) { 98 l++, r--; 99 } 100 else if (s[l] == char('a' + c)) { 101 cnt++, l++; 102 } 103 else if (s[r] == char('a' + c)) { 104 cnt++, r--; 105 } 106 else { 107 cnt = n + 1; 108 break; 109 } 110 } 111 ans = min(ans, cnt); 112 } 113 if (ans == n + 1) ans = -1; 114 cout << ans << '\n'; 115 } 116 return 0; 117 } 118 ``` 119 120 [1582D - Vupsen, Pupsen and 0](/contest/1582/problem/D "Codeforces Round 750 (Div. 2)") 121 122 Idea: [AlFlen](/profile/AlFlen "Master AlFlen") 123 124 **Tutorial** 125 126 Tutorial is loading... 127 128 **Solution (AlFlen)** 129 130 ``` 131 ttt = int(input()) 132 for t in range(ttt): 133 n = int(input()) 134 a = [int(x) for x in input().split()] 135 start = 0 136 if n % 2 == 1: 137 if (a[0] + a[1] != 0): 138 print(-a[2], -a[2], a[0] + a[1], end = " ") 139 elif (a[1] + a[2] != 0): 140 print(a[2] + a[1], -a[0], -a[0], end = " ") 141 else: 142 print(-a[1], a[0] + a[2], -a[1], end = " ") 143 start = 3 144 while start < n: 145 print(-a[s + 1], a[s], end = " ") 146 start += 2 147 print() 148 ``` 149 150 [1582E - Pchelyonok and Segments](/contest/1582/problem/E "Codeforces Round 750 (Div. 2)") 151 152 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR") 153 154 **Tutorial** 155 156 Tutorial is loading... 157 158 **Solution (74TrAkToR)** 159 160 ``` 161 #include<bits/stdc++.h> 162 163 using namespace std; 164 165 typedef long long ll; 166 int const maxn = 1e5 + 5, maxk = 450; 167 int a[maxn], dp[maxn][maxk]; 168 int inf = 1e9 + 7; 169 ll pref[maxn]; 170 171 main() { 172 ios_base::sync_with_stdio(0); 173 cin.tie(0); 174 cout.tie(0); 175 int t, n; 176 cin >> t; 177 while (t--) { 178 cin >> n; 179 for (int i = 1; i <= n; ++i) { 180 cin >> a[i]; 181 pref[i] = pref[i - 1] + a[i]; 182 } 183 int k = 0; 184 while (k * (k + 1) / 2 <= n) k++; 185 for (int j = 0; j < k; ++j) { 186 dp[n + 1][j] = -inf; 187 } 188 dp[n + 1][0] = inf; 189 for (int i = n; i >= 1; --i) { 190 for (int j = 0; j < k; ++j) { 191 dp[i][j] = dp[i + 1][j]; 192 if (j && i + j - 1 <= n && pref[i + j - 1] - pref[i - 1] < dp[i + j][j - 1]) { 193 dp[i][j] = max(dp[i][j], (int)(pref[i + j - 1] - pref[i - 1])); 194 } 195 } 196 } 197 int ans = 0; 198 for (int j = 0; j < k; ++j) { 199 if (dp[1][j] > 0) ans = j; 200 } 201 cout << ans << '\n'; 202 } 203 return 0; 204 } 205 ``` 206 207 [1582F2 - Korney Korneevich and XOR (hard version)](/contest/1582/problem/F2 "Codeforces Round 750 (Div. 2)") 208 209 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution (74TrAkToR)** 216 217 ``` 218 #include<bits/stdc++.h> 219 220 using namespace std; 221 222 int const max_value = (1 << 13); 223 vector < int > g[max_value]; 224 int ans[max_value], r[max_value]; 225 226 int main() { 227 ios_base::sync_with_stdio(0); 228 cin.tie(0); 229 cout.tie(0); 230 int n, x; 231 cin >> n; 232 ans[0] = 1; 233 for (int i = 0; i < max_value; ++i) { 234 g[i].push_back(0); 235 } 236 for (int i = 0; i < max_value; ++i) { 237 r[i] = max_value; 238 } 239 for (int i = 1; i <= n; ++i) { 240 cin >> x; 241 for (auto key : g[x]) { 242 int to = (key^x); 243 ans[to] = 1; 244 while (r[to] > x) { 245 r[to]--; 246 if (r[to] != x) g[r[to]].push_back(to); 247 } 248 } 249 g[x] = {}; 250 } 251 int k = 0; 252 for (int i = 0; i < max_value; ++i) { 253 k += ans[i]; 254 } 255 cout << k << '\n'; 256 for (int i = 0; i < max_value; ++i) { 257 if (ans[i]) cout << i << " "; 258 } 259 cout << '\n'; 260 return 0; 261 } 262 ``` 263 264 [1582G - Kuzya and Homework](/contest/1582/problem/G "Codeforces Round 750 (Div. 2)") 265 266 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution (74TrAkToR)** 273 274 ``` 275 #include<bits/stdc++.h> 276 277 using namespace std; 278 279 typedef long long ll; 280 281 int const maxn = 1e6 + 5; 282 int a[maxn]; 283 int prime[maxn]; 284 int L[maxn]; 285 vector < int > pos[maxn]; 286 287 inline void add(int x, int l) { 288 L[l] = l; 289 while (x > 1) { 290 pos[prime[x]].push_back(l); 291 x /= prime[x]; 292 } 293 } 294 295 inline void del(int x, int l) { 296 if (x == 1) { 297 L[l] = l; 298 return; 299 } 300 L[l] = l; 301 while (x > 1) { 302 if ((int)pos[prime[x]].size() == 0) { 303 L[l] = 0; 304 return; 305 } 306 L[l] = min(L[l], pos[prime[x]].back()); 307 pos[prime[x]].pop_back(); 308 x /= prime[x]; 309 } 310 } 311 312 int main() { 313 ios_base::sync_with_stdio(0); 314 cin.tie(0); 315 cout.tie(0); 316 317 int n; 318 cin >> n; 319 for (int i = 1; i <= n; ++i) cin >> a[i]; 320 321 for (int i = 2; i < maxn; ++i) { 322 if (prime[i] == 0) { 323 prime[i] = i; 324 if (i > 1000) continue; 325 for (int j = i * i; j < maxn; j += i) { 326 prime[j] = i; 327 } 328 } 329 } 330 331 char type; 332 for (int i = 1; i <= n; ++i) { 333 cin >> type; 334 if (type == '*') add(a[i], i); 335 else del(a[i], i); 336 } 337 338 ll answer = 0; 339 vector < pair < int, int > > f_min; 340 for (int i = n; i >= 1; --i) { 341 int cnt = 1; 342 while ((int)f_min.size() > 0 && f_min.back().first >= L[i]) { 343 cnt += f_min.back().second; 344 f_min.pop_back(); 345 } 346 f_min.push_back({L[i], cnt}); 347 if (L[i] == i) answer += (ll)cnt; 348 } 349 cout << answer << '\n'; 350 return 0; 351 } 352 ```