codeforces-scrape

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

976.md (8090B)


      1 Source: https://codeforces.com/blog/entry/59195
      2 
      3 [976A - Minimum Binary Number](/contest/976/problem/A "Educational Codeforces Round 43 (Rated for Div. 2)")
      4 
      5 **Editorial**
      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 	string s;
     24 	cin >> n >> s;
     25 	if (n == 1) {
     26 		cout << s << endl;
     27 	} else {
     28 		int cnt0 = 0;
     29 		for (int i = 0; i < n; ++i)
     30 			cnt0 += s[i] == '0';
     31 		cout << 1;
     32 		for (int i = 0; i < cnt0; ++i)
     33 			cout << 0;
     34 		cout << endl;
     35 	}
     36 	
     37 	return 0;
     38 }
     39 ```
     40 
     41 [976B - Lara Croft and the New Game](/contest/976/problem/B "Educational Codeforces Round 43 (Rated for Div. 2)")
     42 
     43 **Editorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution (PikMike)**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 
     52 #define forn(i, n) for (int i = 0; i < int(n); i++)
     53 
     54 using namespace std;
     55 
     56 int n, m;
     57 long long k;
     58 
     59 int main() {
     60 	scanf("%d%d%lld", &n, &m, &k);
     61 	if (k < n){
     62 		printf("%lld 1\n", k + 1);
     63 		return 0;
     64 	}
     65 	k -= n;
     66 	long long row = k / (m - 1);
     67 	printf("%lld ", n - row);
     68 	if (row & 1)
     69 		printf("%lld\n", m - k % (m - 1));
     70 	else
     71 		printf("%lld\n", k % (m - 1) + 2);
     72 	return 0;
     73 }
     74 ```
     75 
     76 [976C - Nested Segments](/contest/976/problem/C "Educational Codeforces Round 43 (Rated for Div. 2)")
     77 
     78 **Editorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution (PikMike)**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 
     87 #define forn(i, n) for (int i = 0; i < int(n); i++)
     88 #define x first
     89 #define y second
     90 
     91 using namespace std;
     92 
     93 typedef pair<int, int> pt;
     94 
     95 const int N = 300 * 1000 + 13;
     96 
     97 int n;
     98 pair<pt, int> a[N];
     99 
    100 int main() {
    101 	scanf("%d", &n);
    102 	forn(i, n){
    103 		scanf("%d%d", &a[i].x.x, &a[i].x.y);
    104 		a[i].y = i + 1;
    105 	}
    106 	
    107 	sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x) return a.x.x < b.x.x; return a.x.y > b.x.y;});
    108 	
    109 	set<pt> cur;
    110 	forn(i, n){
    111 		while (!cur.empty() && cur.begin()->x < a[i].x.x)
    112 			cur.erase(cur.begin());
    113 		if (!cur.empty() && (--cur.end())->x >= a[i].x.y){
    114 			printf("%d %d\n", a[i].y, (--cur.end())->y);
    115 			return 0;
    116 		}
    117 		cur.insert({a[i].x.y, a[i].y});
    118 	}
    119 	
    120 	puts("-1 -1");
    121 	return 0;
    122 }
    123 ```
    124 
    125 [976D - Degree Set](/contest/976/problem/D "Educational Codeforces Round 43 (Rated for Div. 2)")
    126 
    127 **Editorial**
    128 
    129 Tutorial is loading...
    130 
    131 **Solution (PikMike)**
    132 
    133 ```
    134 #include <bits/stdc++.h>
    135 
    136 #define forn(i, n) for (int i = 0; i < int(n); i++)
    137 
    138 using namespace std;
    139 
    140 typedef pair<int, int> pt;
    141 
    142 const int N = 100 * 1000 + 13;
    143 
    144 int n;
    145 vector<int> d;
    146 vector<int> g[N];
    147 
    148 vector<pt> construct(int st, vector<int> d){
    149 	if (d.empty())
    150 		return vector<pt>();
    151 	
    152 	vector<pt> res;
    153 	forn(i, d[0])
    154 		for (int j = st + i + 1; j <= st + d.back(); ++j)
    155 			res.push_back({st + i, j});
    156 	
    157 	int nxt = st + d[0];
    158 	for (int i = 1; i < int(d.size()); ++i)
    159 		d[i] -= d[0];
    160 	d.erase(d.begin());
    161 	if (!d.empty())
    162 		d.pop_back();
    163 	
    164 	auto tmp = construct(nxt, d);
    165 	for (auto it : tmp)
    166 		res.push_back(it);
    167 	
    168 	return res;
    169 }
    170 
    171 int main() {
    172 	scanf("%d", &n);
    173 	d.resize(n);
    174 	forn(i, n)
    175 		scanf("%d", &d[i]);
    176 	auto res = construct(0, d);
    177 	printf("%d\n", int(res.size()));
    178 	for (auto it : res)
    179 		printf("%d %d\n", it.first + 1, it.second + 1);
    180 	return 0;
    181 }
    182 ```
    183 
    184 [976E - Well played!](/contest/976/problem/E "Educational Codeforces Round 43 (Rated for Div. 2)")
    185 
    186 **Editorial**
    187 
    188 Tutorial is loading...
    189 
    190 **Solution (Ajosteen)**
    191 
    192 ```
    193 #include <bits/stdc++.h>
    194 
    195 using namespace std;
    196 
    197 const int N = 200 * 1000 + 9;
    198 
    199 int n, a, b;
    200 int hp[N], dmg[N];
    201 
    202 bool cmp(int i, int j){
    203 	if(hp[i] - dmg[i] != hp[j] - dmg[j])
    204 		return hp[i] - dmg[i] > hp[j] - dmg[j];
    205 	return i < j;
    206 }
    207 
    208 int get(int id){
    209 	return  hp[id] > dmg[id]? hp[id] : dmg[id];
    210 }
    211 
    212 int main(){
    213 	scanf("%d %d %d", &n, &a, &b);
    214 	for(int i = 0; i < n; ++i)
    215 		scanf("%d %d", hp + i, dmg + i);
    216 	
    217 	b = min(b, n);
    218 	vector <int> p(n);
    219 	for(int i = 0; i < n; ++i) p[i] = i;
    220 	sort(p.begin(), p.end(), cmp);
    221 	long long res = 0, sum = 0;
    222 	for(int i = 0; i < n; ++i){
    223 		int id = p[i];
    224 		if(i < b) sum += get(id);
    225 		else sum += dmg[id];
    226 	}
    227 	res = sum; 
    228 
    229 	if(b == 0){
    230 		printf("%lld\n", res);
    231 		return 0;
    232 	}
    233 	
    234 	long long x = (1LL << a);
    235 	for(int i = 0; i < n; ++i){
    236 		int id = p[i];
    237 		long long nres = sum;
    238 		if(i < b){ 
    239 			nres -= get(id);
    240 			nres += hp[id] * x;
    241 			res = max(res, nres);
    242 		}
    243 		else{
    244 			nres -= dmg[id];
    245 			nres += hp[id] * x;			
    246 			int id2 = p[b - 1];
    247 			nres -= get(id2);
    248 			nres += dmg[id2];
    249 			res = max(res, nres);
    250 			
    251 		}		
    252 	}
    253 	
    254 	printf("%lld\n", res);
    255 	return 0;
    256 }
    257 ```
    258 
    259 [976F - Minimal k-covering](/contest/976/problem/F "Educational Codeforces Round 43 (Rated for Div. 2)")
    260 
    261 **Editorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution (adedalic)**
    266 
    267 ```
    268 #include<bits/stdc++.h>
    269 
    270 using namespace std;
    271 
    272 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    273 
    274 #define sz(a) int((a).size())
    275 #define x first
    276 #define y second
    277 
    278 const int INF = int(1e9);
    279 const int N = 4221;
    280 
    281 struct edge {
    282     int to, c, f, id;
    283 
    284     edge(int to = 0, int c = 0, int f = 0, int id = -1) : to(to), c(c), f(f), id(id) {}
    285 };
    286 
    287 vector<edge> es;
    288 vector<int> g[N];
    289 
    290 void add_edge(int fr, int to, int cap, int id) {
    291     g[fr].push_back(sz(es));
    292     es.emplace_back(to, cap, 0, id);
    293     g[to].push_back(sz(es));
    294     es.emplace_back(fr, 0, 0, id);
    295 }
    296 
    297 int pw[N];
    298 int n1, n2, m;
    299 
    300 inline bool read() {
    301     if(!(cin >> n1 >> n2 >> m))
    302         return false;
    303 
    304     fore(id, 0, m) {
    305         int u, v;
    306         assert(cin >> u >> v);
    307         u--, v--;
    308 
    309         pw[u]++;
    310         pw[n1 + v]++;
    311 
    312         add_edge(u, n1 + v, 1, id);
    313     }
    314     return true;
    315 }
    316 
    317 int d[N], q[N], hd, tl;
    318 inline bool bfs(int s, int t, int n) {
    319     fore(i, 0, n)
    320         d[i] = INF;
    321     hd = tl = 0;
    322 
    323     d[s] = 0;
    324     q[tl++] = s;
    325     while(hd != tl) {
    326         int v = q[hd++];
    327         if(v == t)
    328             break;
    329 
    330         for(int id : g[v]) {
    331             if(es[id].c - es[id].f == 0)
    332                 continue;
    333 
    334             int to = es[id].to;
    335             if(d[to] > d[v] + 1) {
    336                 d[to] = d[v] + 1;
    337                 q[tl++] = to;
    338             }
    339         }
    340     }
    341     return d[t] < INF;
    342 }
    343 
    344 int nxt[N];
    345 
    346 int dfs(int v, int t, int mx) {
    347     if(v == t) return mx;
    348     if(mx == 0) return 0;
    349 
    350     int sum = 0;
    351     for(; nxt[v] < sz(g[v]); nxt[v]++) {
    352         int id = g[v][nxt[v]];
    353         int rem = es[id].c - es[id].f;
    354         int to = es[id].to;
    355 
    356         if(rem == 0 || d[to] != d[v] + 1)
    357             continue;
    358 
    359         int cur = 0;
    360         if((cur = dfs(to, t, min(mx - sum, rem))) > 0) {
    361             es[id].f += cur;
    362             es[id ^ 1].f -= cur;
    363             sum += cur;
    364         }
    365 
    366         if(sum == mx)
    367             break;
    368     }
    369     return sum;
    370 }
    371 
    372 inline int dinic(int s, int t, int n) {
    373     int mf = 0;
    374     while(bfs(s, t, n)) {
    375         fore(i, 0, n)
    376             nxt[i] = 0;
    377 
    378         int cf = 0;
    379         while((cf = dfs(s, t, INF)) > 0)
    380             mf += cf;
    381     }
    382     return mf;
    383 }
    384 
    385 vector<int> res[N];
    386 
    387 inline void getCert(int k) {
    388     fore(v, 0, n1) {
    389         for(int id : g[v]) {
    390             if(es[id].to < n1 || es[id].to >= n1 + n2)
    391                 continue;
    392             assert(es[id].c > 0);
    393             if(es[id].f > 0)
    394                 continue;
    395 
    396             res[k].push_back(es[id].id);
    397         }
    398     }
    399 }
    400 
    401 void solve() {
    402     int cnt = *min_element(pw, pw + n1 + n2);
    403 
    404     int s = n1 + n2; int t = s + 1;
    405     fore(i, 0, n1)
    406         add_edge(s, i, pw[i] - cnt, -1);
    407     fore(i, n1, n1 + n2)
    408         add_edge(i, t, pw[i] - cnt, -1);
    409 
    410     int mf = 0, mn = cnt;
    411     while(mn >= 0) {
    412         mf += dinic(s, t, n1 + n2 + 2);
    413         getCert(mn);
    414 
    415         if(mn > 0) {
    416             for (int id : g[s]) {
    417                 assert(es[id].id < 0);
    418                 assert((id & 1) == 0);
    419                 es[id].c++;
    420             }
    421             for (int id : g[t]) {
    422                 assert(es[id].id < 0);
    423                 assert(es[id].c == 0);
    424                 es[id ^ 1].c++;
    425             }
    426         }
    427         mn--;
    428     }
    429 
    430     fore(i, 0, cnt + 1) {
    431         printf("%d ", sz(res[i]));
    432         for(int id : res[i])
    433             printf("%d ", id + 1);
    434         puts("");
    435     }
    436 }
    437 
    438 int main() {
    439 #ifdef _DEBUG
    440     freopen("input.txt", "r", stdin);
    441 #endif
    442 
    443     if(read()) {
    444         solve();
    445     }
    446     return 0;
    447 }
    448 ```