codeforces-scrape

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

1978.md (7174B)


      1 Source: https://codeforces.com/blog/entry/130527
      2 
      3 Tutorial is loading...
      4 
      5 **Code**
      6 
      7 ```
      8 #include <random>
      9 #include <vector>
     10 #include <iostream>
     11 #include <set>
     12 #include <map>
     13 #include <algorithm>
     14  
     15 using namespace std;
     16  
     17 #define fi first
     18 #define se second
     19 #define all(x) (x).begin(), (x).end()
     20 #define ll long long
     21 #define pii pair<int, int>
     22 #define pb emplace_back
     23  
     24 int main() {
     25     int t;
     26     cin >> t;
     27     while (t--) {
     28         int n;
     29         cin >> n;
     30         vector<int> a(n);
     31         for (auto &c : a) cin >> c;
     32         int mx = 0;
     33         for (int i = 0; i < n - 1; i++) mx = max(mx, a[i]);
     34         cout << mx + a[n - 1] << "\n";
     35     }
     36     return 0;
     37 }
     38 ```
     39 
     40 Tutorial is loading...
     41 
     42 **Code**
     43 
     44 ```
     45 #include <iostream>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50     int t;
     51     cin >> t;
     52     while (t--) {
     53         long long n, a, b;
     54         cin >> n >> a >> b;
     55         if (b <= a) {
     56             cout << n * a << endl;
     57         } else {
     58             long long k = min(b &mdash; a + 1, n);
     59             cout << (b &mdash; k + 1) * n + k * (k &mdash; 1) / 2 << endl;
     60         }
     61     }
     62 }
     63 ```
     64 
     65 Tutorial is loading...
     66 
     67 **Code**
     68 
     69 ```
     70 #include <bits/stdc++.h>
     71 using namespace std;
     72 typedef long long ll;
     73 int main() {
     74     ios::sync_with_stdio(false);
     75     cin.tie(0), cout.tie(0);
     76     int T = 1;
     77     cin >> T;
     78     while (T--) {
     79         int n;
     80         ll k;
     81         cin >> n >> k;
     82         ll max_s = 0;
     83         for (int i = 0; i < n; i++) max_s += abs(n &mdash; 1 &mdash; i &mdash; i);
     84         if (k % 2 != 0 || k > max_s) {
     85             cout << "No\n";
     86         } else {
     87             cout << "Yes\n";
     88             vector<int> p(n);
     89             k /= 2;
     90             iota(p.begin(), p.end(), 0);
     91             for (int i = 0; k > 0; i++) {
     92                 if (k >= n &mdash; 1 &mdash; 2 * i) {
     93                     swap(p[i], p[n &mdash; 1 &mdash; i]);
     94                     k -= n &mdash; 1 &mdash; 2 * i;
     95                 } else {
     96                     swap(p[i], p[i + k]);
     97                     k = 0;
     98                 }
     99             }
    100             for (int i = 0; i < n; i++) {
    101                 cout << p[i] + 1 << " ";
    102             }
    103             cout << "\n";
    104         }
    105     }
    106 }
    107 ```
    108 
    109 Tutorial is loading...
    110 
    111 **Code**
    112 
    113 ```
    114 #include <bits/stdc++.h>
    115 
    116 using namespace std;
    117 using ll = long long;
    118 
    119 void solve() {
    120     int n, c;
    121     cin >> n >> c;
    122 
    123     vector<int> a(n);
    124     for (int i = 0; i < n; ++i) {
    125         cin >> a[i];
    126     }
    127 
    128     if (n == 1) {
    129         cout << "0\n";
    130         return;
    131     }
    132 
    133     int mx = *max_element(a.begin() + 1, a.end());
    134     int mxc = max(a[0] + c, mx);
    135     int winner = mxc == a[0] + c ? 0 : find(a.begin() + 1, a.end(), mx) - a.begin();
    136     ll sum = c;
    137     for (int i = 0; i < n; sum += a[i], ++i) {
    138         int answer;
    139         if (i == winner) {
    140             answer = 0;
    141         } else if (sum + a[i] >= mx) {
    142             answer = i;
    143         } else {
    144             answer = i + 1;
    145         }
    146         cout << answer << " \n"[i == n - 1];
    147     }
    148 }
    149 
    150 int main() {
    151     ios::sync_with_stdio(false);
    152     cin.tie(nullptr);
    153 
    154     int test = 1;
    155     cin >> test;
    156     
    157     while (test--) {
    158         solve();
    159     }
    160 
    161     return 0;
    162 }
    163 ```
    164 
    165 Tutorial is loading...
    166 
    167 **Code**
    168 
    169 ```
    170 #include <bits/stdc++.h>
    171 using namespace std;
    172  
    173 int main () {
    174   ios_base::sync_with_stdio(0); cin.tie(0);
    175   int T;
    176   cin >> T;
    177   while (T--) {
    178     int n;
    179     string s, t;
    180     cin >> n >> s >> t;
    181     auto get_range = [&] (int i) {
    182       if (s[i] == '1') return make_pair(i, i);
    183       int l = -1, r = -1;
    184       if (i > 0 && t[i-1] == '1') l = i-1;
    185       else if (i > 1 && t[i-1] == '0' && s[i-2] == '0') l = i-2;
    186       if (i+1 < n && t[i+1] == '1') r = i+1;
    187       else if (i+2 < n && t[i+1] == '0' && s[i+2] == '0') r = i+2;
    188       if (l == -1) r = -1;
    189       if (r == -1) l = -1;
    190       return make_pair(l, r);
    191     };
    192  
    193     vector<int> pref(n+1);
    194     for (int i = 0; i < n; i++) pref[i+1] = pref[i] + (get_range(i).first != -1);
    195  
    196     int q;
    197     cin >> q;
    198     while (q--) {
    199       int l, r;
    200       cin >> l >> r;
    201       int ans = 0;
    202       if (r-l <= 5) {
    203         for (int i = l-1; i < r; i++) {
    204           auto [ll, rr] = get_range(i);
    205           if (ll >= l-1 && rr < r) ans++;
    206         }
    207       }
    208       else {
    209         ans = pref[r] - pref[l-1];
    210         for (int j: {l-1, l, r-2, r-1}) {
    211           auto [ll, rr] = get_range(j);
    212           if (ll != -1 && (ll < l-1 || rr >= r)) ans--;
    213         }
    214       }
    215       cout << ans << '\n';
    216     }
    217   }
    218 }
    219 ```
    220 
    221 Tutorial is loading...
    222 
    223 **Code**
    224 
    225 ```
    226 #include <iostream>
    227 #include <vector>
    228 #include <map>
    229 #include <set>
    230 #include <queue>
    231 #include <algorithm>
    232 #include <string>
    233 #include <cmath>
    234 #include <cstdio>
    235 #include <iomanip>
    236 #include <fstream>
    237 #include <cassert>
    238 #include <cstring>
    239 #include <unordered_set>
    240 #include <unordered_map>
    241 #include <numeric>
    242 #include <ctime>
    243  
    244 using namespace std;
    245  
    246 using ll = long long;
    247  
    248 const int MAXA = 1e6;
    249  
    250 int n, k;
    251 vector<int> a;
    252 vector<int> primes_x[MAXA + 1];
    253 unordered_map<int, int> last_ind_p;
    254 vector<bool> is_prime(MAXA + 1, true);
    255 vector<int> primes;
    256  
    257 void read() {
    258 	cin >> n >> k;
    259 	a.assign(n, 0);
    260 	for (int& elem : a) {
    261 		cin >> elem;
    262 	}
    263 }
    264  
    265 vector<int> p, sz, p_rs;
    266  
    267 int col(int A) {
    268 	return (A == p[A] ? A : p[A] = col(p[A]));
    269 }
    270  
    271 void unique(int A, int B) {
    272 	A = col(A); B = col(B);
    273 	if (A == B) return;
    274 	if (sz[A] < sz[B]) {
    275 		swap(A, B);
    276 	}
    277 	p[B] = A;
    278 	sz[A] += sz[B];
    279 }
    280  
    281 void solve() {
    282     last_ind_p.clear();
    283 	vector<int> aa;
    284 	for (int i = 1; i < n; i++) {
    285 		aa.push_back(a[i]);
    286 	}
    287 	for (int i = 0; i < n; i++) {
    288 		aa.push_back(a[i]);
    289 	}
    290 	a = aa;
    291 	int n2 = n;
    292 	n = a.size();
    293 	p.assign(n, -1);
    294 	p_rs.assign(n, -1);
    295 	sz.assign(n, -1);
    296 	for (int i = 0; i < n; i++) {
    297 		p[i] = i;
    298 		sz[i] = 1;
    299 	}
    300  
    301 	for (int i = 0; i < n2; i++) {
    302 		p_rs[i] = i + 1;
    303 		p_rs[2 * n2 - 2 - i] = i + 1;
    304 	}
    305 	vector<int> a2 = a;
    306 	sort(a2.begin(), a2.end());
    307 	a2.resize(unique(a2.begin(), a2.end()) - a2.begin());
    308     unordered_set<int> to_clean;
    309 	for (int elem : a2) {
    310 		int cur_elem = elem;
    311 		for (ll p : primes) {
    312 			if (p * p > elem) break;
    313 			if (elem % p == 0) {
    314 				primes_x[cur_elem].push_back(p);
    315                 if (primes_x[cur_elem].size() == 1) {
    316                     to_clean.insert(cur_elem);
    317                 }
    318 			}
    319 			while (elem % p == 0) {
    320 				elem /= p;
    321 			}
    322 		}
    323 		if (elem > 1) {
    324 			primes_x[cur_elem].push_back(elem);
    325             if (primes_x[cur_elem].size() == 1) {
    326                 to_clean.insert(cur_elem);
    327             }
    328 		}
    329 	}
    330  
    331 	for (int i = 0; i < n; i++) {
    332 		for (int cur_p : primes_x[a[i]]) {
    333 			if (last_ind_p.count(cur_p) && i - last_ind_p[cur_p] <= k) {
    334 				unique(last_ind_p[cur_p], i);
    335 			}
    336 			last_ind_p[cur_p] = i;
    337 		}
    338 	}
    339     for (int i : to_clean)
    340         primes_x[i].clear();
    341 }
    342  
    343 void write() {
    344 	ll ans = 0;
    345 	for (int i = 0; i < n; i++) {
    346 		if (p[i] == i) {
    347 			if (a[i] > 1) {
    348 				ans += 1;
    349 			}
    350 			else {
    351 				ans += p_rs[i];
    352 			}
    353 		}
    354 	}
    355 	cout << ans << endl;
    356 }
    357  
    358 int main() {
    359     for (ll i = 2; i <= MAXA; i++) {
    360         if (is_prime[i]) {
    361             primes.push_back(i);
    362             for (ll j = i * i; j <= MAXA; j += i) {
    363                 is_prime[j] = false;
    364             }
    365         }
    366     }
    367 	ios_base::sync_with_stdio(false); cin.tie(0);
    368     int t;
    369     cin >> t;
    370     while (t--) {
    371         read();
    372         solve();
    373         write();
    374     }
    375 }
    376 ```