codeforces-scrape

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

1217.md (7992B)


      1 Source: https://codeforces.com/blog/entry/69605
      2 
      3 [1217A - Creating a Character](/contest/1217/problem/A "Educational Codeforces Round 72 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (adedalic)**
     10 
     11 ```
     12 fun main() {
     13     val t = readLine()!!.toInt()
     14     for (ct in 1..t) {
     15         val (str, int, exp) = readLine()!!.split(' ').map { it.toInt() }
     16         val minAddStr = maxOf(0, (exp + int - str + 2) / 2)
     17         println(maxOf(exp - minAddStr + 1, 0))
     18     }
     19 }
     20 ```
     21 
     22 [1217B - Zmei Gorynich](/contest/1217/problem/B "Educational Codeforces Round 72 (Rated for Div. 2)")
     23 
     24 Idea: [Roms](/profile/Roms "Master Roms")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (Roms)**
     31 
     32 ```
     33 #include <bits/stdc++.h>
     34 
     35 using namespace std;
     36 
     37 const int N = 105;
     38 
     39 int t;
     40 int n, m;
     41 int d[N], h[N];
     42 
     43 int main() {
     44 	cin >> t;
     45 	for(int tc = 0; tc < t; ++tc){
     46 		cin >> n >> m;
     47 		int maxDH = -2e9;
     48 		for(int i = 0; i < n; ++i){
     49 			cin >> d[i] >> h[i];
     50 			maxDH = max(maxDH, d[i] - h[i]);
     51 		}
     52 
     53 		int res = 1;	
     54 		int maxD = *max_element(d, d + n);
     55 		m -= maxD;
     56 		if(m > 0){
     57 			if(maxDH <= 0) res = -1;
     58 			else res += (m + maxDH - 1) / maxDH; 	
     59 		}	
     60 		cout << res << endl;
     61 	}
     62 	
     63 	return 0;
     64 }
     65 ```
     66 
     67 [1217C - The Number Of Good Substrings](/contest/1217/problem/C "Educational Codeforces Round 72 (Rated for Div. 2)")
     68 
     69 Idea: [Roms](/profile/Roms "Master Roms")
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution (Roms)**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 const int N = int(3e5) + 99;
     83 
     84 int t;
     85 string s;
     86 int nxt[N];
     87 
     88 int main() {
     89 	cin >> t;
     90 	for(int tc = 0; tc < t; ++tc){
     91 		cin >> s;
     92 		for(int i = 0; i < s.size(); ++i)
     93 			if(s[i] == '1') nxt[i] = i;
     94 			else nxt[i] = (i == 0? -1 : nxt[i - 1]);		
     95 		int res = 0;
     96 		for(int r = 0; r < s.size(); ++r){
     97 			int sum = 0;
     98 			for(int l = r; l >= 0 && r - l < 20; --l){
     99 				if(s[l] == '0') continue;
    100 				sum += 1 << (r - l);
    101 				if(sum <= r - (l == 0? -1 : nxt[l - 1]))
    102 					++res;
    103 			}
    104 		}
    105 		cout << res << endl;
    106 	}	
    107 
    108 	return 0;
    109 }
    110 ```
    111 
    112 [1217D - Coloring Edges](/contest/1217/problem/D "Educational Codeforces Round 72 (Rated for Div. 2)")
    113 
    114 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    115 
    116 **Tutorial**
    117 
    118 Tutorial is loading...
    119 
    120 **Solution (Roms)**
    121 
    122 ```
    123 #include<bits/stdc++.h>
    124 
    125 using namespace std;
    126 
    127 const int N = int(1e6) + 55;
    128 
    129 int n, m;
    130 vector <pair<int, int> > g[N];
    131 int col[N];
    132 bool cyc;
    133 int res[N];
    134 
    135 void dfs(int v){
    136 	col[v] = 1;
    137 	for(auto p : g[v]){
    138 		int to = p.first, id = p.second;
    139 		if(col[to] == 0){
    140 			dfs(to);
    141 			res[id] = 1;
    142 		}
    143 		else if(col[to] == 2)
    144 			res[id] = 1;
    145 		else{
    146 			res[id] = 2;
    147 			cyc = true;
    148 		}
    149 	}
    150 	col[v] = 2;
    151 }
    152 
    153 int main(){
    154 	cin >> n >> m;
    155 	for(int i = 0; i < m; ++i){
    156 		int u, v;
    157 		cin >> u >> v;
    158 		--u, --v;
    159 		g[u].push_back(make_pair(v, i));
    160 	}
    161 	
    162 	for(int i = 0; i < n; ++i)
    163 			if(col[i] == 0)
    164 				dfs(i);
    165 			
    166 	cout << (cyc? 2 : 1) << endl;
    167 	for(int i = 0; i < m; ++i) cout << res[i] << ' ';
    168 	cout << endl;
    169 	return 0;
    170 }
    171 ```
    172 
    173 [1217E - Sum Queries?](/contest/1217/problem/E "Educational Codeforces Round 72 (Rated for Div. 2)")
    174 
    175 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    176 
    177 **Tutorial**
    178 
    179 Tutorial is loading...
    180 
    181 **Solution (PikMike)**
    182 
    183 ```
    184 #include <bits/stdc++.h>
    185 
    186 #define forn(i, n) for (int i = 0; i < int(n); i++)
    187 
    188 using namespace std;
    189 
    190 const int N = 200 * 1000 + 13;
    191 const int INF = 2e9;
    192 const int LOGN = 9;
    193 
    194 struct node{
    195 	int best;
    196 	int mn[LOGN];
    197 	node(){
    198 		best = INF;
    199 		forn(i, LOGN)
    200 			mn[i] = INF;
    201 	}
    202 	int& operator [](int x){
    203 		return mn[x];
    204 	}
    205 };
    206 
    207 int a[N];
    208 node t[4 * N];
    209 
    210 void upd(node &t, int val){
    211 	int x = val;
    212 	forn(i, LOGN){
    213 		if (x % 10 != 0)
    214 			t[i] = min(t[i], val);
    215 		x /= 10;
    216 	}
    217 }
    218 
    219 node merge(node &a, node &b){
    220 	node c;
    221 	c.best = min(a.best, b.best);
    222 	forn(i, LOGN){
    223 		c[i] = min(a[i], b[i]);
    224 		if (a[i] < INF && b[i] < INF)
    225 			c.best = min(c.best, a[i] + b[i]);
    226 	}
    227 	return c;
    228 }
    229 
    230 void build(int v, int l, int r){
    231 	if (l == r - 1){
    232 		t[v] = node();
    233 		upd(t[v], a[l]);
    234 		return;
    235 	}
    236 	int m = (l + r) / 2;
    237 	build(v * 2, l, m);
    238 	build(v * 2 + 1, m, r);
    239 	t[v] = merge(t[v * 2], t[v * 2 + 1]);
    240 }
    241 
    242 void upd(int v, int l, int r, int pos, int val){
    243 	if (l == r - 1){
    244 		t[v] = node();
    245 		upd(t[v], val);
    246 		return;
    247 	}
    248 	int m = (l + r) / 2;
    249 	if (pos < m)
    250 		upd(v * 2, l, m, pos, val);
    251 	else
    252 		upd(v * 2 + 1, m, r, pos, val);
    253 	t[v] = merge(t[v * 2], t[v * 2 + 1]);
    254 }
    255 
    256 node get(int v, int l, int r, int L, int R){
    257 	if (l == L && r == R)
    258 		return t[v];
    259 	int m = (l + r) / 2;
    260 	if (R <= m)
    261 		return get(v * 2, l, m, L, R);
    262 	if (L >= m)
    263 		return get(v * 2 + 1, m, r, L, R);
    264 	node ln = get(v * 2, l, m, L, m);
    265 	node rn = get(v * 2 + 1, m, r, m, R);
    266 	return merge(ln, rn);
    267 }
    268 
    269 int main() {
    270 	int n, m;
    271 	scanf("%d%d", &n, &m);
    272 	forn(i, n)
    273 		scanf("%d", &a[i]);
    274 	build(1, 0, n);
    275 	forn(i, m){
    276 		int t, x, y;
    277 		scanf("%d%d%d", &t, &x, &y);
    278 		--x;
    279 		if (t == 1)
    280 			upd(1, 0, n, x, y);
    281 		else{
    282 			node res = get(1, 0, n, x, y);
    283 			printf("%d\n", res.best == INF ? -1 : res.best);
    284 		}
    285 	}
    286 	return 0;
    287 }
    288 ```
    289 
    290 [1217F - Forced Online Queries Problem](/contest/1217/problem/F "Educational Codeforces Round 72 (Rated for Div. 2)")
    291 
    292 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    293 
    294 **Tutorial**
    295 
    296 Tutorial is loading...
    297 
    298 **Solution (PikMike)**
    299 
    300 ```
    301 #include <bits/stdc++.h>
    302 
    303 #define forn(i, n) for (int i = 0; i < int(n); i++)
    304 
    305 using namespace std;
    306 
    307 const int BUF = 10 * 1000 * 1000 + 13;
    308 const int N = 300 * 1000 + 13;
    309 const int M = 300 * 1000 + 13;
    310 const int P = 400;
    311 
    312 struct query{
    313 	int t, x, y;
    314 	int e0, e1;
    315 };
    316 
    317 int n, m;
    318 query q[M];
    319 
    320 int p[N], rk[N];
    321 
    322 int cnt;
    323 int* where[BUF];
    324 int val[BUF];
    325 
    326 void rollback(){
    327 	while (cnt > 0){
    328 		*where[cnt - 1] = val[cnt - 1];
    329 		--cnt;
    330 	}
    331 }
    332 
    333 int getp(int a){
    334 	return (a == p[a] ? a : getp(p[a]));
    335 }
    336 
    337 void unite(int a, int b){
    338 	a = getp(a), b = getp(b);
    339 	if (a == b) return;
    340 	if (rk[a] < rk[b]) swap(a, b);
    341 	where[cnt] = &rk[a];
    342 	val[cnt++] = rk[a];
    343 	where[cnt] = &p[b];
    344 	val[cnt++] = p[b];
    345 	assert(cnt <= BUF);
    346 	rk[a] += rk[b];
    347 	p[b] = a;
    348 }
    349 
    350 int getpFast(int a){
    351 	return (a == p[a] ? a : p[a] = getpFast(p[a]));
    352 }
    353 
    354 void uniteFast(int a, int b){
    355 	a = getpFast(a), b = getpFast(b);
    356 	if (a == b) return;
    357 	if (rk[a] < rk[b]) swap(a, b);
    358 	rk[a] += rk[b];
    359 	p[b] = a;
    360 }
    361 
    362 struct edge{
    363 	int v, u;
    364 };
    365 
    366 bool operator <(const edge &a, const edge &b){
    367 	if (a.v != b.v)
    368 		return a.v < b.v;
    369 	return a.u < b.u;
    370 }
    371 
    372 edge edges[2 * M];
    373 map<edge, int> rev;
    374 
    375 bool used[2 * M];
    376 bool state[2 * M];
    377 int ans[M];
    378 vector<int> cur;
    379 
    380 void rebuild(int l){
    381 	int r = min(m, l + P);
    382 	forn(i, n) p[i] = i, rk[i] = 1;
    383 	memset(used, 0, sizeof(used));
    384 	memset(state, 0, sizeof(state));
    385 
    386 	forn(i, l) if (q[i].t == 1){
    387 		int e = (ans[i] ? q[i].e1 : q[i].e0);
    388 		used[e] = true;
    389 		state[e] ^= 1;
    390 	}
    391 	
    392 	for (int i = l; i < r; ++i) if (q[i].t == 1)
    393 		used[q[i].e0] = used[q[i].e1] = false;
    394 	
    395 	cur.clear();
    396 	cnt = 0;
    397 	forn(i, l) if (q[i].t == 1){
    398 		int e = (ans[i] ? q[i].e1 : q[i].e0);
    399 		if (used[e] && state[e]){
    400 			state[e] = false;
    401 			uniteFast(edges[e].v, edges[e].u);
    402 		}
    403 		else if (!used[e] && state[e]){
    404 			state[e] = false;
    405 			cur.push_back(e);
    406 		}
    407 	}
    408 }
    409 
    410 int get_edge(edge e){
    411 	if (!rev.count(e)){
    412 		int k = rev.size();
    413 		edges[k] = e;
    414 		rev[e] = k;
    415 	}
    416 	return rev[e];
    417 }
    418 
    419 int main(){
    420 	scanf("%d%d", &n, &m);
    421 	forn(i, m){
    422 		scanf("%d%d%d", &q[i].t, &q[i].x, &q[i].y);
    423 		--q[i].x, --q[i].y;
    424 		if (q[i].t == 1){
    425 			edge e({q[i].x, q[i].y});
    426 			if (e.v > e.u) swap(e.v, e.u);
    427 			q[i].e0 = get_edge(e);
    428 			e.v = (e.v + 1) % n, e.u = (e.u + 1) % n;
    429 			if (e.v > e.u) swap(e.v, e.u);
    430 			q[i].e1 = get_edge(e);
    431 		}
    432 	}
    433 	
    434 	string res = "";
    435 	ans[0] = 0;
    436 	forn(i, m){
    437 		if (i % P == 0)
    438 			rebuild(i);
    439 		
    440 		int x = (q[i].x + ans[i]) % n;
    441 		int y = (q[i].y + ans[i]) % n;
    442 		if (x > y) swap(x, y);
    443 		
    444 		if (q[i].t == 1){
    445 			rollback();
    446 			int e = get_edge({x, y});
    447 			auto it = find(cur.begin(), cur.end(), e);
    448 			if (it == cur.end())
    449 				cur.push_back(e);
    450 			else
    451 				cur.erase(it);
    452 			ans[i + 1] = ans[i];
    453 		}
    454 		else{
    455 			for (auto e : cur)
    456 				unite(edges[e].v, edges[e].u);
    457 			bool rc = (getp(x) == getp(y));
    458 			ans[i + 1] = rc;
    459 			res += ('0' + rc);
    460 		}
    461 	}
    462 	
    463 	puts(res.c_str());
    464 	return 0;
    465 }
    466 ```