codeforces-scrape

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

1851.md (9732B)


      1 Source: https://codeforces.com/blog/entry/118667
      2 
      3 [1851A - Escalator Conversations](/contest/1851/problem/A "Codeforces Round 888 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Aris](/profile/Aris "Candidate Master Aris")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 #define sz(v) (int)v.size()
     20 #define all(v) v.begin(),v.end()
     21 #define eb emplace_back
     22 
     23 void solve() {
     24     int n,m,k,H; cin >> n >> m >> k >> H;
     25     int ans = 0;
     26     forn(i, n) {
     27         int x; cin >> x;
     28         ans += (H != x) && abs(H - x) % k == 0 && abs(H-x) <= (m-1) * k;
     29     }
     30     cout << ans << endl;
     31 }
     32 
     33 int main() {
     34     int t;
     35     cin >> t;
     36 
     37     forn(tt, t) {
     38         solve();
     39     }
     40 }
     41 ```
     42 
     43 [1851B - Parity Sort](/contest/1851/problem/B "Codeforces Round 888 (Div. 3)")
     44 
     45 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [myav](/profile/myav "Pupil myav")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution**
     52 
     53 ```
     54 #include<bits/stdc++.h>
     55 using namespace std;
     56 
     57 bool solve(){
     58     int n;
     59     cin >> n;
     60     vector<int>a(n), b(n);
     61     for(int i = 0; i < n; i++){
     62         cin >> a[i];
     63         b[i] = a[i];
     64     }
     65     sort(b.begin(), b.end());
     66     for(int i = 0; i < n; i++){
     67         if((a[i] % 2) != (b[i] % 2)) return false;
     68     }
     69     return true;
     70 
     71 }
     72 
     73 int main(){
     74     int t;
     75     cin >> t;
     76     while(t--){
     77         cout << (solve() ? "YES" : "NO") << "\n";
     78     }
     79     return 0;
     80 }
     81 ```
     82 
     83 [1851C - Tiles Comeback](/contest/1851/problem/C "Codeforces Round 888 (Div. 3)")
     84 
     85 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [myav](/profile/myav "Pupil myav")
     86 
     87 **Tutorial**
     88 
     89 Tutorial is loading...
     90 
     91 **Solution**
     92 
     93 ```
     94 #include "bits/stdc++.h"
     95 using namespace std;
     96 
     97 bool solve(){
     98     int n, k;
     99     cin >> n >> k;
    100     vector<int>c(n);
    101     for(int i = 0; i < n; i++) cin >> c[i];
    102     int left = 0, right = 0, i = 0, j = n - 1;
    103     int k_left = k, k_right = k;
    104 
    105     if (c[0] == c[n - 1]){
    106         k_left = k / 2;
    107         k_right = k - k_left;
    108     }
    109     for(; i < n && left < k_left; i++){
    110         if(c[i] == c[0]) left++;
    111     }
    112     for(; j >= 0 && right < k_right; j--){
    113         if(c[j] == c[n - 1]) right++;
    114     }
    115     return (i - 1) < (j + 1);
    116 }
    117 
    118 int main(){
    119     int t;
    120     cin >> t;
    121     while(t--){
    122         cout << (solve() ? "YES" : "NO") << "\n";
    123     }
    124 
    125 }
    126 ```
    127 
    128 [1851D - Prefix Permutation Sums](/contest/1851/problem/D "Codeforces Round 888 (Div. 3)")
    129 
    130 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    131 
    132 **Tutorial**
    133 
    134 Tutorial is loading...
    135 
    136 **Solution**
    137 
    138 ```
    139 #include <iostream>
    140 #include <vector>
    141 #include <set>
    142 #include <map>
    143 
    144 using namespace std;
    145 
    146 typedef long long ll;
    147 
    148 ll n;
    149 
    150 bool isPermutation(vector<ll> a) {
    151     for (int i = 0; i < n; ++i) {
    152         if (a[i] <= 0 || a[i] > n) {
    153             return false;
    154         }
    155     }
    156     set<ll> s(a.begin(), a.end());
    157     return s.size() == n;
    158 }
    159 
    160 vector<ll> prefSumToArray(vector<ll> p) {
    161     vector<ll> res(n);
    162     res[0] = p[0];
    163     for (int i = 1; i < n; ++i) {
    164         res[i] = p[i] - p[i - 1];
    165     }
    166     return res;
    167 }
    168 
    169 void solve() {
    170     cin >> n;
    171     vector<ll> a(n - 1);
    172     for (int i = 0; i + 1 < n; ++i) {
    173         cin >> a[i];
    174     }
    175     ll x = n * (n + 1) / 2;
    176     if (a.back() != x) {
    177         a.push_back(x);
    178         vector<ll> b = prefSumToArray(a);
    179         if (isPermutation(b)) {
    180             cout << "YES\n";
    181         } else {
    182             cout << "NO\n";
    183         }
    184         return;
    185     }
    186     map<ll, int> cnt;
    187     cnt[a[0]]++;
    188     for (int i = 1; i < n - 1; ++i) {
    189         cnt[a[i] - a[i - 1]]++;
    190     }
    191     vector<int> cntGt1;
    192     for (auto p: cnt) {
    193         if (p.second > 1) {
    194             cntGt1.push_back(p.first);
    195         }
    196     }
    197     if (cntGt1.size() > 1) {
    198         cout << "NO\n";
    199         return;
    200     }
    201     if (cntGt1.size() == 1) {
    202         int x1 = cntGt1[0];
    203         if (cnt[x1] > 2) {
    204             cout << "NO\n";
    205             return;
    206         }
    207     }
    208     vector<int> cnt0;
    209     for (int i = 1; i <= n; ++i) {
    210         if (cnt[i] == 0) {
    211             cnt0.push_back(i);
    212         }
    213     }
    214     if (cnt0.size() != 2) {
    215         cout << "NO\n";
    216         return;
    217     }
    218     cout << "YES\n";
    219 }
    220 
    221 int main() {
    222     ios_base::sync_with_stdio(0);
    223     cin.tie(0), cout.tie(0);
    224     int t;
    225     cin >> t;
    226     for (int _ = 0; _ < t; ++_) {
    227         solve();
    228     }
    229     return 0;
    230 }
    231 ```
    232 
    233 [1851E - Nastya and Potions](/contest/1851/problem/E "Codeforces Round 888 (Div. 3)")
    234 
    235 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    236 
    237 **Tutorial**
    238 
    239 Tutorial is loading...
    240 
    241 **Solution**
    242 
    243 ```
    244 #include <bits/stdc++.h>
    245 
    246 #define int long long
    247 
    248 using namespace std;
    249 
    250 vector<int> dp;
    251 vector<bool> used;
    252 vector<vector<int>> sl;
    253 
    254 int get(int v){
    255     if(used[v]){
    256         return dp[v];
    257     }
    258     used[v] = true;
    259     int s = 0;
    260     for(int u: sl[v]){
    261         s += get(u);
    262     }
    263     if(!sl[v].empty()) dp[v] = min(dp[v], s);
    264     return dp[v];
    265 }
    266 
    267 void solve(int tc) {
    268     int n, k;
    269     cin >> n >> k;
    270     dp.resize(n);
    271     used.assign(n, false);
    272     sl.assign(n, vector<int>(0));
    273     for(int &e: dp) cin >> e;
    274     for(int i = 0; i < k; ++i){
    275         int e;
    276         cin >> e;
    277         dp[--e] = 0;
    278     }
    279     for(int i = 0; i < n; ++i){
    280         int m;
    281         cin >> m;
    282         sl[i].resize(m);
    283         for(int &e: sl[i]){
    284             cin >> e;
    285             --e;
    286         }
    287     }
    288     for(int i = 0; i < n; ++i){
    289         get(i);
    290     }
    291     for(int e: dp) cout << e << " ";
    292 }
    293 
    294 bool multi = true;
    295 
    296 signed main() {
    297     int t = 1;
    298     if(multi) cin >> t;
    299     for (int i = 1; i <= t; ++i) {
    300         solve(i);
    301         cout << "\n";
    302     }
    303     return 0;
    304 }
    305 ```
    306 
    307 [1851F - Lisa and the Martians](/contest/1851/problem/F "Codeforces Round 888 (Div. 3)")
    308 
    309 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    310 
    311 **Tutorial**
    312 
    313 Tutorial is loading...
    314 
    315 **Solution**
    316 
    317 ```
    318 #include <bits/stdc++.h>
    319 #define all(arr) arr.begin(), arr.end()
    320 
    321 using namespace std;
    322 
    323 const int MAXN = 200200;
    324 const int MAXK = 30;
    325 const int MAXMEM = MAXN * MAXK;
    326 
    327 mt19937 rng(07062006);
    328 
    329 struct node {
    330 	node *chi[2] {nullptr};
    331 	int sz = 0, id = -1;
    332 };
    333 
    334 int n, k;
    335 int arr[MAXN];
    336 node *mem = new node[MAXMEM];
    337 node *root, *mpos;
    338 
    339 void add_num(node* &v, int val, int i, int id) {
    340 	if (v == nullptr) *(v = mpos++) = node();
    341 	v->sz++;
    342 	if (i == -1) {
    343 		v->id = id;
    344 		return;
    345 	}
    346 	add_num(v->chi[val >> i & 1], val, i - 1, id);
    347 }
    348 
    349 int down(node *v, int val, int i, int &x, int &jans) {
    350 	if (i == -1) {
    351 		jans = v->id;
    352 		return 0;
    353 	}
    354 	int b = val >> i & 1;
    355 	if (v->chi[b])
    356 		return down(v->chi[b], val, i - 1, x ^= ((1 ^ b) << i), jans) | (1 << i);
    357 	return down(v->chi[b ^ 1], val, i - 1, x ^= ((rng() & 1) << i), jans);
    358 }
    359 
    360 void build() {
    361 	root = nullptr;
    362 	mpos = mem;
    363 	add_num(root, *arr, k - 1, 0);
    364 }
    365 
    366 tuple<int, int, int> solve() {
    367 	int ians = 0, jans = 1, xans = 0;
    368 	for (int i = 1; i < n; ++i) {
    369 		int x = 0, j = -1;
    370 		int cur = down(root, arr[i], k - 1, x, j);
    371 		if (cur > ((arr[ians] ^ xans) & (arr[jans] ^ xans)))
    372 			ians = j, jans = i, xans = x;
    373 		add_num(root, arr[i], k - 1, i);
    374 	}
    375 	return {ians, jans, xans};
    376 }
    377 
    378 int main() {
    379 	int t; cin >> t;
    380 	while (t--) {
    381 		cin >> n >> k;
    382 		for (int i = 0; i < n; ++i)
    383 			cin >> arr[i];
    384 		build();
    385 		auto [ians, jans, xans] = solve();
    386 		cout << ++ians << ' ' << ++jans << ' ' << xans << endl;
    387 	}
    388 }
    389 ```
    390 
    391 [1851G - Vlad and the Mountains](/contest/1851/problem/G "Codeforces Round 888 (Div. 3)")
    392 
    393 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    394 
    395 **Tutorial**
    396 
    397 Tutorial is loading...
    398 
    399 **Solution**
    400 
    401 ```
    402 #include <bits/stdc++.h>
    403 
    404 #define x first
    405 #define y second
    406 #define all(a) a.begin(), a.end()
    407 #define rall(a) a.rbegin(), a.rend()
    408 
    409 typedef long double ld;
    410 typedef long long ll;
    411 
    412 using namespace std;
    413 
    414 struct dsu{
    415     vector<int> p, lvl;
    416 
    417     dsu(int n){
    418         p.resize(n);
    419         lvl.assign(n, 0);
    420         iota(all(p), 0);
    421     }
    422 
    423     int get(int i){
    424         if(i == p[i]) return i;
    425         return p[i] = get(p[i]);
    426     }
    427 
    428     bool unite(int a, int b){
    429         a = get(a);
    430         b = get(b);
    431         if(a == b){
    432             return false;
    433         }
    434         if(lvl[a] < lvl[b])swap(a, b);
    435         p[b] = a;
    436         if(lvl[a] == lvl[b]){
    437             ++lvl[a];
    438         }
    439         return true;
    440     }
    441 
    442     bool reachable(int a, int b){
    443         return get(a) == get(b);
    444     }
    445 };
    446 
    447 void solve(int tc) {
    448     int n, m;
    449     cin >> n >> m;
    450     vector<pair<int, int>> h(n);
    451     for(auto &e: h) cin >> e.x;
    452     for(int i = 0; i < n; ++i){
    453         h[i].y = i;
    454     }
    455     dsu graph(n);
    456     vector<vector<int>> sl(n);
    457     for(int i = 0; i < m; ++i){
    458         int u, v;
    459         cin >> u >> v;
    460         --u, --v;
    461         if(h[u].x > h[v].x) sl[u].emplace_back(v);
    462         else sl[v].emplace_back(u);
    463     }
    464     int q;
    465     cin >> q;
    466     vector<pair<pair<int, int>, pair<int, int>>> req(q);
    467     for(auto &e: req){
    468         cin >> e.y.x >> e.y.y >> e.x.x;
    469         --e.y.x, --e.y.y;
    470         e.x.x += h[e.y.x].x;
    471     }
    472     for(int i = 0; i < q; ++i){
    473         req[i].x.y = i;
    474     }
    475 
    476     sort(all(h));
    477     sort(all(req));
    478     vector<bool> ans(q);
    479     int j = 0;
    480     for(auto e: req){
    481         while (j < n && h[j].x <= e.x.x) {
    482             for(int u: sl[h[j].y]){
    483                 graph.unite(h[j].y, u);
    484             }
    485             ++j;
    486         }
    487         ans[e.x.y] = graph.reachable(e.y.x, e.y.y);
    488     }
    489     for(bool e: ans) cout << (e? "YES": "NO") << "\n";
    490 }
    491 
    492 bool multi = true;
    493 
    494 signed main() {
    495     int t = 1;
    496     if(multi) cin >> t;
    497     for (int i = 1; i <= t; ++i) {
    498         solve(i);
    499         if(i < t) cout << "\n";
    500     }
    501     return 0;
    502 }
    503 ```