codeforces-scrape

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

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 ```