codeforces-scrape

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

1006.md (7102B)


      1 Source: https://codeforces.com/blog/entry/60672
      2 
      3 [1006A - Adjacent Replacements](/contest/1006/problem/A "Codeforces Round 498 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int n;
     23 	cin >> n;
     24 	for (int i = 0; i < n; ++i) {
     25 		int x;
     26 		cin >> x;
     27 		cout << x - !(x & 1) << " ";
     28 	}
     29 	
     30 	return 0;
     31 }
     32 ```
     33 
     34 [1006B - Polycarp's Practice](/contest/1006/problem/B "Codeforces Round 498 (Div. 3)")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (Vovuh)**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44 
     45 using namespace std;
     46 
     47 int main() {
     48 #ifdef _DEBUG
     49 	freopen("input.txt", "r", stdin); 
     50 //	freopen("output.txt", "w", stdout);
     51 #endif
     52 	
     53 	int n, k;
     54 	cin >> n >> k;
     55 	vector<pair<int, int>> res(n);
     56 	vector<int> a(n); 
     57 	for (int i = 0; i < n; ++i) {
     58 		cin >> res[i].first;
     59 		a[i] = res[i].first;
     60 		res[i].second = i + 1;
     61 	}
     62 	
     63 	sort(res.begin(), res.end());
     64 	reverse(res.begin(), res.end());
     65 	sort(res.begin(), res.begin() + k, [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; });
     66 	
     67 	int lst = 0, sum = 0;
     68 	for (int i = 0; i < k - 1; ++i) {
     69 	    sum += *max_element(a.begin() + lst, a.begin() + res[i].second);
     70 		lst = res[i].second;	
     71 	}
     72 	sum += *max_element(a.begin() + lst, a.end());
     73 	cout << sum << endl;
     74 	
     75 
     76 	lst = 0;
     77 	for (int i = 0; i < k - 1; ++i) {
     78 		cout << res[i].second - lst << " ";
     79 		lst = res[i].second;	
     80 	}
     81 	cout << n - lst << endl;
     82 	
     83 	return 0;
     84 }
     85 ```
     86 
     87 [1006C - Three Parts of the Array](/contest/1006/problem/C "Codeforces Round 498 (Div. 3)")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (Vovuh, set)**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97 
     98 using namespace std;
     99 
    100 int main() {
    101 #ifdef _DEBUG
    102 	freopen("input.txt", "r", stdin);
    103 //	freopen("output.txt", "w", stdout);
    104 #endif
    105 	
    106 	int n;
    107 	cin >> n;
    108 	vector<int> a(n);
    109 	for (int i = 0; i < n; ++i)
    110 		cin >> a[i];
    111 		
    112 	set<long long> sum;
    113 	long long l = 0;
    114 	for (int i = 0; i < n; ++i) {
    115 		l += a[i];
    116 		sum.insert(l);
    117 	}
    118 	
    119 	long long ans = 0;
    120 	long long r = 0;
    121 	for (int i = n - 1; i >= 0; --i) {
    122 		sum.erase(l);
    123 		l -= a[i];
    124 		r += a[i];
    125 		if (sum.count(r))
    126 			ans = max(ans, r);
    127 	}
    128 	
    129 	cout << ans << endl;
    130 	
    131 	return 0;
    132 }
    133 ```
    134 
    135 **Solution (ivan100sic, two pointers)**
    136 
    137 ```
    138 #include <bits/stdc++.h>
    139 using namespace std;
    140 
    141 typedef long long ll;
    142 typedef unsigned long long ull;
    143 typedef long double ld;
    144 
    145 int n;
    146 int a[200005];
    147 
    148 int main() {
    149 	ios_base::sync_with_stdio(false);
    150 	cin.tie(nullptr);
    151 	cout.tie(nullptr);
    152 	cerr.tie(nullptr);
    153 
    154 	cin >> n;
    155 	for (int i=1; i<=n; i++)
    156 		cin >> a[i];
    157 
    158 	int i = 0, j = n+1;
    159 	ll zi = 0, zj = 0, solidx = 0;
    160 	while (i < j) {
    161 		if (zi < zj)
    162 			zi += a[++i];
    163 		else if (zi > zj)
    164 			zj += a[--j];
    165 		else {
    166 			solidx = i;
    167 			zi += a[++i];
    168 			zj += a[--j];
    169 		}
    170 	}
    171 	
    172 	cout << accumulate(a+1, a+solidx+1, 0ll); // here
    173 }
    174 ```
    175 
    176 [1006D - Two Strings Swaps](/contest/1006/problem/D "Codeforces Round 498 (Div. 3)")
    177 
    178 **Tutorial**
    179 
    180 Tutorial is loading...
    181 
    182 **Solution (Ne0n25)**
    183 
    184 ```
    185 #include <bits/stdc++.h>
    186  
    187 using namespace std;
    188  
    189 #define x first
    190 #define y second
    191 #define mp make_pair
    192 #define pb push_back
    193 #define sqr(a) ((a) * (a))
    194 #define sz(a) int(a.size())
    195 #define all(a) a.begin(), a.end()
    196 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    197 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    198  
    199 typedef long long li;
    200 typedef long double ld;
    201 typedef pair<int, int> pt;
    202  
    203 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    204 	return out << "(" << a.x << ", " << a.y << ")";
    205 }
    206  
    207 template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    208 	out << "[";
    209 	forn(i, sz(v)) {
    210 		if(i) out << ", ";
    211 		out << v[i];
    212 	}
    213 	return out << "]";
    214 }
    215  
    216 mt19937 rnd(time(NULL));
    217  
    218 const int INF = int(1e9);
    219 const li INF64 = li(1e18);
    220 const int MOD = INF + 7;
    221 const ld EPS = 1e-9;
    222 const ld PI = acos(-1.0);
    223  
    224 int n;
    225 string s, t;
    226 
    227 bool read() {
    228 	if (!(cin >> n >> s >> t))
    229 		return false;
    230 	return true;
    231 }
    232 
    233 void solve() {
    234 	int ans = 0;
    235 	forn(i, n / 2) {
    236 		map<char, int> a;
    237 		a[s[i]]++; a[s[n - i - 1]]++;
    238 		a[t[i]]++; a[t[n - i - 1]]++;
    239 		if (sz(a) == 4)
    240 			ans += 2;
    241 		else if (sz(a) == 3)
    242 			ans += 1 + (s[i] == s[n - i - 1]);
    243 		else if (sz(a) == 2)
    244 			ans += a[s[i]] != 2;
    245 	}
    246 	
    247 	if (n % 2 == 1 && s[n / 2] != t[n / 2])
    248 		ans++;
    249 		
    250 	cout << ans << endl;
    251 }
    252  
    253 int main() {
    254 #ifdef _DEBUG
    255 	freopen("input.txt", "r", stdin);
    256 //	freopen("output.txt", "w", stdout);
    257  
    258 	int tt = clock();
    259  
    260 #endif
    261  
    262 	cerr.precision(15);
    263 	cout.precision(15);
    264 	cerr << fixed;
    265 	cout << fixed;
    266 	
    267 #ifdef _DEBUG
    268 	while (read()) {	
    269 #else
    270 	if (read()) {
    271 #endif
    272 		solve();
    273  
    274 #ifdef _DEBUG
    275 	cerr << "TIME = " << clock() - tt << endl;
    276 	tt = clock();
    277 #endif
    278  
    279 	}
    280 }
    281 ```
    282 
    283 [1006E - Military Problem](/contest/1006/problem/E "Codeforces Round 498 (Div. 3)")
    284 
    285 **Tutorial**
    286 
    287 Tutorial is loading...
    288 
    289 **Solution (mareksom)**
    290 
    291 ```
    292 #include <bits/stdc++.h>
    293 
    294 using namespace std;
    295 
    296 int n, q;
    297 vector<vector<int>> tree;
    298 
    299 int current_preorder;
    300 vector<int> preorder, max_preorder;
    301 vector<int> sorted_by_preorder;
    302 
    303 void Dfs(int w) {
    304   sorted_by_preorder[current_preorder] = w;
    305   preorder[w] = current_preorder++;
    306   for (int c : tree[w]) {
    307     Dfs(c);
    308   }
    309   max_preorder[w] = current_preorder - 1;
    310 }
    311 
    312 int main() {
    313   ios_base::sync_with_stdio(0);
    314   cin.tie(0);
    315   cin >> n >> q;
    316   assert(2 <= n);
    317   assert(1 <= q);
    318   tree.resize(n);
    319   for (int i = 1; i < n; i++) {
    320     int p;
    321     cin >> p;
    322     p--;
    323     assert(0 <= p and p < n);
    324     tree[p].push_back(i);
    325   }
    326 
    327   preorder.resize(n);
    328   max_preorder.resize(n);
    329   sorted_by_preorder.resize(n);
    330   current_preorder = 0;
    331   Dfs(0);
    332 
    333   for (int i = 0; i < q; i++) {
    334     int u, k;
    335     cin >> u >> k;
    336     u--; k--;
    337     assert(0 <= u and u < n);
    338     assert(0 <= k and k < n);
    339     k += preorder[u];
    340     int answer = -1;
    341     if (k <= max_preorder[u]) {
    342       answer = sorted_by_preorder[k] + 1;
    343       assert(1 <= answer and answer <= n);
    344     }
    345     cout << answer << '\n';
    346   }
    347   return 0;
    348 }
    349 ```
    350 
    351 [1006F - Xor-Paths](/contest/1006/problem/F "Codeforces Round 498 (Div. 3)")
    352 
    353 **Tutorial**
    354 
    355 Tutorial is loading...
    356 
    357 **Solution (Vovuh)**
    358 
    359 ```
    360 #include <bits/stdc++.h>
    361 
    362 using namespace std;
    363 
    364 const int N = 20;
    365 
    366 map<long long, int> v[N][N];
    367 
    368 int n, m;
    369 int half;
    370 long long k;
    371 long long a[N][N];
    372 long long ans;
    373 
    374 void calclf(int x, int y, long long val, int cnt) {
    375 	val ^= a[x][y];
    376 	if (cnt == half) {
    377 		++v[x][y][val];
    378 		return;
    379 	}
    380 	if (x + 1 < n)
    381 		calclf(x + 1, y, val, cnt + 1);
    382 	if (y + 1 < m)
    383 		calclf(x, y + 1, val, cnt + 1);
    384 }
    385 
    386 void calcrg(int x, int y, long long val, int cnt) {
    387 	if (cnt == n + m - 2 - half) {
    388 		if (v[x][y].count(k ^ val))
    389 			ans += v[x][y][k ^ val];
    390 		return;
    391 	}
    392 	if (x > 0)
    393 		calcrg(x - 1, y, val ^ a[x][y], cnt + 1);
    394 	if (y > 0)
    395 		calcrg(x, y - 1, val ^ a[x][y], cnt + 1);
    396 }
    397 
    398 int main() {
    399 #ifdef _DEBUG
    400 	freopen("input.txt", "r", stdin);
    401 //	freopen("output.txt", "w", stdout);
    402 #endif
    403 	
    404 	cin >> n >> m >> k;
    405 	half = (n + m - 2) / 2;
    406 	for (int i = 0; i < n; ++i) {
    407 		for (int j = 0; j < m; ++j) {
    408 			cin >> a[i][j];
    409 		}
    410 	}
    411 	
    412 	calclf(0, 0, 0, 0);
    413 	calcrg(n - 1, m - 1, 0, 0);
    414 	
    415 	cout << ans << endl;
    416 	
    417 	return 0;
    418 }
    419 ```