1849.md (7899B)
1 Source: https://codeforces.com/blog/entry/118752 2 3 [1849A - Morning Sandwich](/contest/1849/problem/A "Educational Codeforces Round 152 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 fun main() = repeat(readLine()!!.toInt()) { 15 val (b, c, h) = readLine()!!.split(' ').map { it.toInt() } 16 println(minOf(b - 1, c + h) * 2 + 1) 17 } 18 ``` 19 20 [1849B - Monsters](/contest/1849/problem/B "Educational Codeforces Round 152 (Rated for Div. 2)") 21 22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (Neon)** 29 30 ``` 31 #include <bits/stdc++.h> 32 33 using namespace std; 34 35 int main() { 36 ios::sync_with_stdio(false); cin.tie(0); 37 int t; 38 cin >> t; 39 while (t--) { 40 int n, k; 41 cin >> n >> k; 42 vector<int> a(n); 43 for (auto &x : a) { 44 cin >> x; 45 x %= k; 46 if (!x) x = k; 47 } 48 vector<int> ord(n); 49 iota(ord.begin(), ord.end(), 0); 50 stable_sort(ord.begin(), ord.end(), [&](int i, int j) { 51 return a[i] > a[j]; 52 }); 53 for (auto &x : ord) cout << x + 1 << ' '; 54 cout << endl; 55 } 56 } 57 ``` 58 59 [1849C - Binary String Copying](/contest/1849/problem/C "Educational Codeforces Round 152 (Rated for Div. 2)") 60 61 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 62 63 **Tutorial** 64 65 Tutorial is loading... 66 67 **Solution (vovuh)** 68 69 ``` 70 #include <bits/stdc++.h> 71 72 using namespace std; 73 74 void solve() { 75 int n, m; 76 string s; 77 cin >> n >> m >> s; 78 79 vector<int> lf(n), rg(n); 80 lf[0] = -1; 81 for (int i = 0; i < n; ++i) { 82 if (i > 0) lf[i] = lf[i - 1]; 83 if (s[i] == '0') lf[i] = i; 84 } 85 rg[n - 1] = n; 86 for (int i = n - 1; i >= 0; --i) { 87 if (i + 1 < n) rg[i] = rg[i + 1]; 88 if (s[i] == '1') rg[i] = i; 89 } 90 91 set<pair<int, int>> st; 92 for (int i = 0; i < m; ++i) { 93 int l, r; 94 cin >> l >> r; 95 int ll = rg[l - 1], rr = lf[r - 1]; 96 if (ll > rr) { 97 st.insert({-1, -1}); 98 } else { 99 st.insert({ll, rr}); 100 } 101 } 102 103 cout << st.size() << endl; 104 } 105 106 int main() { 107 #ifdef _DEBUG 108 freopen("input.txt", "r", stdin); 109 // freopen("output.txt", "w", stdout); 110 #endif 111 int t; 112 cin >> t; 113 while (t--) solve(); 114 } 115 ``` 116 117 [1849D - Array Painting](/contest/1849/problem/D "Educational Codeforces Round 152 (Rated for Div. 2)") 118 119 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 120 121 **Tutorial** 122 123 Tutorial is loading... 124 125 **Solution (BledDest)** 126 127 ``` 128 n = int(input()) 129 a = list(map(int, input().split())) 130 131 ans = 0 132 l = 0 133 while l < n: 134 r = l + 1 135 hasTwo = (a[l] == 2) 136 hasMiddleZero = False 137 while r < n: 138 if r - 1 > l and a[r - 1] == 0: 139 hasMiddleZero = True 140 if a[r] == 2: 141 hasTwo = True 142 good = (not hasMiddleZero) and (hasTwo or a[l] != 0 or a[r] != 0) 143 if not good: 144 break 145 r += 1 146 l = r 147 ans += 1 148 149 print(ans) 150 ``` 151 152 [1849E - Max to the Right of Min](/contest/1849/problem/E "Educational Codeforces Round 152 (Rated for Div. 2)") 153 154 Idea: [awoo](/profile/awoo "Grandmaster awoo") 155 156 **Tutorial** 157 158 Tutorial is loading... 159 160 **Solution (awoo)** 161 162 ``` 163 #include <bits/stdc++.h> 164 165 using namespace std; 166 167 bool comp(const pair<int, int> &a, const pair<int, int> &b){ 168 return a.second < b.second; 169 } 170 171 int main(){ 172 int n; 173 scanf("%d", &n); 174 vector<pair<int, int>> stmn, stmx; 175 stmn.push_back({-1, -1}); 176 stmx.push_back({n, -1}); 177 long long ans = 0; 178 int len = 0; 179 set<pair<int, int>> cur; 180 cur.insert({-1, 0}); 181 cur.insert({-1, 1}); 182 for (int i = 0; i < n; ++i){ 183 int x; 184 scanf("%d", &x); 185 --x; 186 187 while (stmn.back().first > x){ 188 auto it = cur.lower_bound({stmn.back().second, 0}); 189 auto me = it; 190 auto prv = it; --prv; 191 ++it; 192 len -= me->first - prv->first; 193 if (it != cur.end() && it->second == 0) 194 len += it->first - prv->first; 195 cur.erase(me); 196 stmn.pop_back(); 197 } 198 len += i - cur.rbegin()->first; 199 cur.insert({i, 0}); 200 stmn.push_back({x, i}); 201 202 while (stmx.back().first < x){ 203 auto it = cur.lower_bound({stmx.back().second, 1}); 204 auto me = it; 205 auto prv = it; --prv; 206 ++it; 207 if (it != cur.end() && it->second == 0) 208 len += me->first - prv->first; 209 cur.erase(me); 210 stmx.pop_back(); 211 } 212 cur.insert({i, 1}); 213 stmx.push_back({x, i}); 214 215 ans += len; 216 } 217 printf("%lld\n", ans - n); 218 } 219 ``` 220 221 [1849F - XOR Partition](/contest/1849/problem/F "Educational Codeforces Round 152 (Rated for Div. 2)") 222 223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 224 225 **Tutorial** 226 227 Tutorial is loading... 228 229 **Solution (BledDest)** 230 231 ``` 232 #include <bits/stdc++.h> 233 234 using namespace std; 235 236 #define pb push_back 237 #define mp make_pair 238 #define forn(i, n) for (int i = 0; i < (int)(n); ++i) 239 typedef long long LL; 240 typedef pair<int, int> PII; 241 242 const int N = 200000; 243 const int NODES = 32 * N; 244 const int INF = int(2e9); 245 246 int n; 247 int a[N]; 248 int nx[NODES][2], cnt[NODES], fn[NODES]; 249 int nodeCount = 1; 250 251 void addInt(int x, int pos) { 252 int ind = 0; 253 for (int i = 29; i >= 0; --i) { 254 int bit = (x >> i) & 1; 255 if (nx[ind][bit] == 0) { 256 nx[ind][bit] = nodeCount++; 257 } 258 ind = nx[ind][bit]; 259 ++cnt[ind]; 260 } 261 fn[ind] = pos; 262 } 263 264 void addInt(int x) { 265 int ind = 0; 266 for (int i = 29; i >= 0; --i) { 267 int bit = (x >> i) & 1; 268 ind = nx[ind][bit]; 269 ++cnt[ind]; 270 } 271 } 272 273 void removeInt(int x) { 274 int ind = 0; 275 for (int i = 29; i >= 0; --i) { 276 int bit = (x >> i) & 1; 277 ind = nx[ind][bit]; 278 --cnt[ind]; 279 } 280 } 281 282 PII findXor(int x) { 283 int ind = 0, res = 0; 284 for (int i = 29; i >= 0; --i) { 285 int bit = (x >> i) & 1; 286 if (cnt[nx[ind][bit]]) { 287 ind = nx[ind][bit]; 288 } else { 289 ind = nx[ind][bit ^ 1]; 290 res |= 1 << i; 291 } 292 } 293 return mp(res, fn[ind]); 294 } 295 296 int par[200000], ra[200000]; 297 298 void dsuInit() { 299 forn(i, n) par[i] = i, ra[i] = 1; 300 } 301 302 int dsuParent(int v) { 303 if (v == par[v]) return v; 304 return par[v] = dsuParent(par[v]); 305 } 306 307 int dsuMerge(int u, int v) { 308 u = dsuParent(u); 309 v = dsuParent(v); 310 if (u == v) return 0; 311 if (ra[u] < ra[v]) swap(u, v); 312 par[v] = u; 313 ra[u] += ra[v]; 314 return 1; 315 } 316 317 vector<int> v[200000]; 318 vector<pair<int, PII> > toMerge; 319 vector<int> g[200000]; 320 int color[200000]; 321 322 void coloring(int x, int c){ 323 if(color[x] != -1) return; 324 color[x] = c; 325 for(auto y : g[x]) coloring(y, c ^ 1); 326 } 327 328 int main() { 329 scanf("%d", &n); 330 forn(i, n) scanf("%d", a + i); 331 forn(i, n) addInt(a[i], i); 332 dsuInit(); 333 for (int merges = 0; merges < n - 1; ) { 334 forn(i, n) v[i].clear(); 335 forn(i, n) v[dsuParent(i)].pb(i); 336 toMerge.clear(); 337 forn(i, n) if (!v[i].empty()) { 338 for (int x : v[i]) { 339 removeInt(a[x]); 340 } 341 pair<pair<int, int>, int> res = mp(mp(INF, INF), INF); 342 for (int x : v[i]) { 343 res = min(res, mp(findXor(a[x]), x)); 344 } 345 toMerge.pb(mp(res.first.first, mp(res.second, res.first.second))); 346 for (int x : v[i]) { 347 addInt(a[x]); 348 } 349 } 350 for (auto p : toMerge) { 351 if (dsuMerge(p.second.first, p.second.second)) { 352 ++merges; 353 g[p.second.first].pb(p.second.second); 354 g[p.second.second].pb(p.second.first); 355 } 356 } 357 } 358 forn(i, n) color[i] = -1; 359 coloring(0, 1); 360 forn(i, n) printf("%d", color[i]); 361 puts(""); 362 return 0; 363 } 364 ```