codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2242.md (10381B)


      1 Source: https://codeforces.com/blog/entry/155047
      2 
      3 [2242A - Bigrams](/contest/2242/problem/A "Educational Codeforces Round 192 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     k = int(input())
     17     a = list(map(int, input().split()))
     18     if max(a) > 2 or a.count(2) > 1:
     19         print('YES')
     20     else:
     21         print('NO')
     22 ```
     23 
     24 [2242B - Predominant Frequency Division](/contest/2242/problem/B "Educational Codeforces Round 192 (Rated for Div. 2)")
     25 
     26 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (FelixArg)**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36  
     37 using namespace std;
     38 
     39 const int INF = 1'000'000'007;
     40  
     41 void solve() {
     42 	int n;
     43 	cin >> n;
     44 	vector<int> a(n);
     45 	for (int i = 0; i < n; i++){
     46 		cin >> a[i];
     47 	}
     48 
     49 	vector<int> pref1(n + 1);
     50 	vector<int> pref2(n + 1);
     51 	for (int i = 0; i < n; i++){
     52 		pref1[i + 1] = pref1[i] + (a[i] == 1 ? 1 : -1);
     53 		pref2[i + 1] = pref2[i] + (a[i] == 3 ? -1 : 1);
     54 	}
     55 
     56 	int mn = INF;
     57 	for (int i = 1; i < n; i++){
     58 		if (pref2[i] - mn >= 0){
     59 			cout << "YES\n";
     60 			return;
     61 		}
     62 		if (pref1[i] >= 0){
     63 			mn = min(mn, pref2[i]);
     64 		}
     65 	}
     66 
     67 	cout << "NO\n";
     68 }
     69 
     70  
     71 signed main()
     72 {
     73 #ifdef FELIX
     74 	auto _clock_start = chrono::high_resolution_clock::now();
     75 #endif
     76 	ios_base::sync_with_stdio(false);
     77 	cin.tie(0);
     78 	cout.tie(0);
     79  
     80 	int tests = 1;
     81 	cin >> tests;
     82 	while(tests--){
     83 		solve();
     84 	}
     85  
     86 #ifdef FELIX
     87 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
     88 		chrono::high_resolution_clock::now()
     89 			- _clock_start).count() << "ms." << endl;
     90 #endif
     91 	return 0;
     92 }
     93 ```
     94 
     95 [2242C - Unstable Elements](/contest/2242/problem/C "Educational Codeforces Round 192 (Rated for Div. 2)")
     96 
     97 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Solution (BledDest)**
    104 
    105 ```
    106 #include <bits/stdc++.h>
    107 
    108 using namespace std;
    109 
    110 void solve() 
    111 {
    112     int n, k;
    113     cin >> n >> k;
    114 
    115     vector<int> a(n);
    116     for (int i = 0; i < n; i++) 
    117     {
    118         cin >> a[i];
    119     }
    120     
    121     vector<int> lens;
    122 
    123     int cur = 1;
    124     for (int i = 1; i < n; i++) 
    125         if (a[i] != a[i - 1]) 
    126         {
    127             lens.push_back(cur);
    128             cur = 1;
    129         } 
    130         else cur++;
    131     lens.push_back(cur);
    132     sort(lens.begin(), lens.end());
    133 
    134     int m = (int)lens.size();
    135     int d = 0;
    136 
    137     int ans = 0;
    138     int i = 0;
    139     while(i < m)
    140     {
    141         int len = lens[i];
    142         int x = len - 1;
    143         int q = m - i;
    144         int curLen = n - d - x * q;
    145         if (curLen <= k && (k - curLen) % q == 0)
    146             ans++;
    147             
    148         int j = i;
    149         while (j < m && lens[j] == len)
    150             j++;
    151         d += (j - i) * lens[i];
    152         i = j;
    153     }
    154 
    155     cout << ans << '\n';
    156 }
    157 
    158 int main() 
    159 {
    160     ios_base::sync_with_stdio(0);
    161     cin.tie(0);
    162     int t;
    163     cin >> t;
    164     for(int i = 0; i < t; i++)
    165         solve();
    166     return 0;
    167 }
    168 ```
    169 
    170 [2242D - Two Digit Strings](/contest/2242/problem/D "Educational Codeforces Round 192 (Rated for Div. 2)")
    171 
    172 Idea: [Roms](/profile/Roms "Master Roms")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution (BledDest)**
    179 
    180 ```
    181 #include<bits/stdc++.h>
    182 
    183 using namespace std;
    184 
    185 const int MOD = 998244353;
    186 
    187 void upd(int& x, int y)
    188 {
    189     if(x < y) x = y;
    190 }
    191 
    192 void solve()
    193 {
    194     string s, t;
    195     cin >> s >> t;
    196     int n = s.size();
    197     int m = t.size();
    198     vector<int> ps(n + 1), pt(m + 1);
    199     for(int i = 0; i < n; i++)
    200         ps[i + 1] = (ps[i] + (s[i] - '0')) % 10;
    201     for(int i = 0; i < m; i++)
    202         pt[i + 1] = (pt[i] + (t[i] - '0')) % 10;
    203     n++;
    204     m++;
    205     if(ps.back() != pt.back())
    206     {
    207         cout << -1 << "\n";
    208         return;
    209     }
    210 
    211     vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    212     for(int i = 0; i <= n; i++)
    213         for(int j = 0; j <= m; j++)
    214         {
    215             if(i < n) upd(dp[i + 1][j], dp[i][j]);
    216             if(j < m) upd(dp[i][j + 1], dp[i][j]);
    217             if(i < n && j < m && ps[i] == pt[j]) upd(dp[i + 1][j + 1], dp[i][j] + 1);
    218         }
    219     cout << dp[n][m] - 1 << "\n";
    220 }
    221 
    222 int main()
    223 {
    224     int t;
    225     cin >> t;
    226     for(int i = 0; i < t; i++)
    227         solve();
    228     return 0;
    229 }
    230 ```
    231 
    232 [2242E - Product of Closures](/contest/2242/problem/E "Educational Codeforces Round 192 (Rated for Div. 2)")
    233 
    234 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    235 
    236 **Tutorial**
    237 
    238 Tutorial is loading...
    239 
    240 **Solution (adedalic)**
    241 
    242 ```
    243 #include<bits/stdc++.h>
    244 
    245 using namespace std;
    246 
    247 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    248 #define sz(a) int((a).size())
    249 
    250 #define x first
    251 #define y second
    252 
    253 typedef long long li;
    254 typedef long double ld;
    255 typedef pair<int, int> pt;
    256 
    257 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    258 	return out << "(" << p.x << ", " << p.y << ")";
    259 }
    260 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    261 	fore(i, 0, sz(v)) {
    262 		if(i) out << " ";
    263 		out << v[i];
    264 	}
    265 	return out;
    266 }
    267 
    268 const int INF = int(1e9);
    269 const li INF64 = li(1e18);
    270 const ld EPS = 1e-9;
    271 
    272 int l, r, n;
    273 
    274 void solve() {
    275 	cin >> l >> r >> n;
    276 	
    277 	int k = 63 - __builtin_clzll(r);
    278 	int x = -1, y = -1;
    279 	if (l >= (1ll << k)) {
    280 		int p = 30;
    281 		while (((l >> p) & 1) == ((r >> p) & 1))
    282 			p--;
    283 		assert(p >= 0);
    284 		x = l;
    285 		y = l - (l & ((1 << p) - 1)) + (1 << p);
    286 	}
    287 	else {
    288 		x = max(l, (1 << (k - 1)));
    289 		y = 1ll << k;
    290 	}
    291 	cerr << l << " " << r << ": " << x << " " << y << endl;
    292 	assert(l <= x && x < y && y <= r);
    293 
    294 	auto getBinary = [](int v) {
    295 		vector<int> rep;
    296 		while (v > 0) {
    297 			rep.push_back(v & 1);
    298 			v >>= 1;
    299 		}
    300 		reverse(rep.begin(), rep.end());
    301 		return rep;
    302 	};
    303 
    304 	auto x_bits = getBinary(x);
    305 	auto y_bits = getBinary(y);
    306 
    307 	string ans(n, '0');
    308 	fore (i, 0, n)
    309 		ans[i] = '0' + (x_bits[i % x_bits.size()] & y_bits[i % y_bits.size()]);
    310 	cout << ans << endl;
    311 }
    312 
    313 int main() {
    314 #ifdef _DEBUG
    315 	freopen("input.txt", "r", stdin);
    316 	int tt = clock();
    317 #endif
    318 	ios_base::sync_with_stdio(false);
    319 	cin.tie(0), cout.tie(0);
    320 	cout << fixed << setprecision(15);
    321 
    322 	int t; cin >> t;
    323 	while (t--) {
    324 		solve();
    325 		
    326 #ifdef _DEBUG
    327 		cerr << "TIME = " << clock() - tt << endl;
    328 		tt = clock();
    329 #endif
    330 	}
    331 	return 0;
    332 }
    333 ```
    334 
    335 [2242F - Summer Vacation](/contest/2242/problem/F "Educational Codeforces Round 192 (Rated for Div. 2)")
    336 
    337 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    338 
    339 **Tutorial**
    340 
    341 Tutorial is loading...
    342 
    343 **Solution (FelixArg)**
    344 
    345 ```
    346 #include <bits/stdc++.h>
    347 
    348 using namespace std;
    349 
    350 mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    351 
    352 const int MX = 200000;
    353 const int REBUILD_EVERY = 5000;
    354 
    355 struct item {
    356     int value, cnt;
    357     int l, r;
    358 
    359     item(): value(0), cnt(0), l(0), r(0) {}
    360     item(int x): value(x), cnt(1), l(0), r(0) {}
    361 };
    362 
    363 vector<item> treap(1);
    364 
    365 int copy(int v) {
    366     treap.push_back(treap[v]);
    367     return int(treap.size()) - 1;
    368 }
    369 
    370 int cnt(int v) {
    371     return v ? treap[v].cnt : 0;
    372 }
    373 
    374 void upd_cnt(int v) {
    375     if (v) {
    376         treap[v].cnt = cnt(treap[v].l) + cnt(treap[v].r) + 1;
    377     }
    378 }
    379 
    380 int merge(int l, int r) {
    381     if (!l || !r) {
    382         return l ? l : r;
    383     }
    384 
    385     int rang = rng() % (cnt(l) + cnt(r));
    386 
    387     if (rang < cnt(l)) {
    388         int res = copy(l);
    389         treap[res].r = merge(treap[res].r, r);
    390         upd_cnt(res);
    391         return res;
    392     } else {
    393         int res = copy(r);
    394         treap[res].l = merge(l, treap[res].l);
    395         upd_cnt(res);
    396         return res;
    397     }
    398 }
    399 
    400 int find_first(int v) {
    401     if (!treap[v].l) {
    402         return treap[v].value;
    403     } else {
    404         return find_first(treap[v].l);
    405     }
    406 }
    407 
    408 void dfs(int v) {
    409     if (!v) {
    410         return;
    411     }
    412 
    413     if (treap[v].l) {
    414         dfs(treap[v].l);
    415     }
    416 
    417     cout << treap[v].value << ' ';
    418 
    419     if (treap[v].r) {
    420         dfs(treap[v].r);
    421     }
    422 }
    423 
    424 pair<int, int> split(int t, int key, int add = 0) {
    425     if (!t) {
    426         return make_pair(0, 0);
    427     }
    428 
    429     t = copy(t);
    430 
    431     int cur_key = add + cnt(treap[t].l);
    432 
    433     if (key <= cur_key) {
    434         auto [l, r] = split(treap[t].l, key, add);
    435         treap[t].l = r;
    436         r = t;
    437         upd_cnt(t);
    438         return {l, r};
    439     } else {
    440         auto [l, r] = split(treap[t].r, key, add + 1 + cnt(treap[t].l));
    441         treap[t].r = l;
    442         l = t;
    443         upd_cnt(t);
    444         return {l, r};
    445     }
    446 }
    447 
    448 int change(int x, int it) {
    449     auto [l, r] = split(it, x, 0);
    450     auto [rl, rr] = split(r, x, 0);
    451     auto [l1, r1] = split(it, MX - x, 0);
    452     return merge(rl, l1);
    453 }
    454 
    455 void collect_values(int v, vector<int>& values) {
    456     if (!v) {
    457         return;
    458     }
    459 
    460     collect_values(treap[v].l, values);
    461     values.push_back(treap[v].value);
    462     collect_values(treap[v].r, values);
    463 }
    464 
    465 int build_balanced(const vector<int>& values, int l, int r) {
    466     if (l >= r) {
    467         return 0;
    468     }
    469 
    470     int m = (l + r) / 2;
    471 
    472     treap.emplace_back(values[m]);
    473     int v = int(treap.size()) - 1;
    474 
    475     treap[v].l = build_balanced(values, l, m);
    476     treap[v].r = build_balanced(values, m + 1, r);
    477 
    478     upd_cnt(v);
    479     return v;
    480 }
    481 
    482 int rebuild(int tr) {
    483     vector<int> values;
    484     values.reserve(cnt(tr));
    485 
    486     collect_values(tr, values);
    487 
    488     treap.clear();
    489     treap.emplace_back();
    490 
    491     return build_balanced(values, 0, int(values.size()));
    492 }
    493 
    494 void solve() {
    495     int n;
    496     cin >> n;
    497 
    498     vector<int> a(n);
    499     for (int i = 0; i < n; i++) {
    500         cin >> a[i];
    501     }
    502 
    503     vector<int> ans(n);
    504 
    505     treap.reserve((size_t)((1 << 25) * 1.5));
    506 
    507     int tr = 0;
    508 
    509     for (int i = 0; i < MX; i++) {
    510         treap.emplace_back(i);
    511         tr = merge(tr, int(treap.size()) - 1);
    512     }
    513 
    514     int changed_iterations = 0;
    515 
    516     for (int i = n - 1; i >= 0; i--) {
    517         tr = change(a[i], tr);
    518         ans[i] = find_first(tr);
    519 
    520         changed_iterations++;
    521 
    522         if (changed_iterations % REBUILD_EVERY == 0) {
    523             tr = rebuild(tr);
    524         }
    525     }
    526 
    527     for (int i = n - 1; i >= 0; i--) {
    528         cout << ans[i] << ' ';
    529     }
    530 }
    531 
    532 signed main() {
    533 #ifdef FELIX
    534     auto _clock_start = chrono::high_resolution_clock::now();
    535 #endif
    536 
    537     ios_base::sync_with_stdio(false);
    538     cin.tie(0);
    539     cout.tie(0);
    540 
    541     int tests = 1;
    542     // cin >> tests;
    543 
    544     while (tests--) {
    545         solve();
    546     }
    547 
    548 #ifdef FELIX
    549     cerr << "Executed in "
    550          << chrono::duration_cast<chrono::milliseconds>(
    551                 chrono::high_resolution_clock::now() - _clock_start
    552             ).count()
    553          << "ms."
    554          << endl;
    555 #endif
    556 
    557     return 0;
    558 }
    559 ```