codeforces-scrape

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

1288.md (11589B)


      1 Source: https://codeforces.com/blog/entry/73105
      2 
      3 [1288A - Deadline](/contest/1288/problem/A "Educational Codeforces Round 80 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	int tt = clock();
     22 #endif
     23 	
     24 	int T; cin >> T;
     25 	while(T--) {
     26 		int n, d;
     27 		cin >> n >> d;
     28 		
     29 		int x, MAG = (int)sqrt(d) + 10;
     30 		for(x = 0; x < MAG; x++) {
     31 			if(x + (d + x) / (x + 1) <= n)
     32 				break;
     33 		}
     34 		cout << (x < MAG ? "YES" : "NO") << endl;
     35 	}
     36 
     37 	return 0;
     38 }
     39 ```
     40 
     41 [1288B - Yet Another Meme Problem](/contest/1288/problem/B "Educational Codeforces Round 80 (Rated for Div. 2)")
     42 
     43 Idea: [Roms](/profile/Roms "Master Roms")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution (Roms)**
     50 
     51 ```
     52 for t in range(int(input())):
     53 	a, b = map(int, input().split())
     54 	print(a * (len(str(b + 1)) - 1))
     55 ```
     56 
     57 [1288C - Two Arrays](/contest/1288/problem/C "Educational Codeforces Round 80 (Rated for Div. 2)")
     58 
     59 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     60 
     61 **Tutorial**
     62 
     63 Tutorial is loading...
     64 
     65 **Solution (Roms)**
     66 
     67 ```
     68 from math import factorial as fact
     69 mod = 10**9 + 7
     70 
     71 def C(n, k):
     72 	return fact(n) // (fact(k) * fact(n - k))
     73 
     74 n, m = map(int, input().split())
     75 print(C(n + 2*m - 1, 2*m) % mod)
     76 ```
     77 
     78 [1288D - Minimax Problem](/contest/1288/problem/D "Educational Codeforces Round 80 (Rated for Div. 2)")
     79 
     80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution (BledDest)**
     87 
     88 ```
     89 #include<bits/stdc++.h>
     90 
     91 using namespace std;
     92 
     93 int n, m;
     94 vector<vector<int> > a;
     95 int a1, a2;
     96 
     97 bool can(int mid)
     98 {
     99     vector<int> msk(1 << m, -1);
    100     for(int i = 0; i < n; i++)
    101     {
    102         int cur = 0;
    103         for(int j = 0; j < m; j++)
    104             if(a[i][j] >= mid)
    105                 cur ^= (1 << j);
    106         msk[cur] = i;
    107     }
    108     if(msk[(1 << m) - 1] != -1)
    109     {
    110         a1 = a2 = msk[(1 << m) - 1];
    111         return true;
    112     }
    113     for(int i = 0; i < (1 << m); i++)
    114         for(int j = 0; j < (1 << m); j++)
    115             if(msk[i] != -1 && msk[j] != -1 && (i | j) == (1 << m) - 1)
    116             {
    117                 a1 = msk[i];
    118                 a2 = msk[j];
    119                 return true;
    120             }
    121     return false;
    122 }
    123 
    124 int main()
    125 {
    126     scanf("%d %d", &n, &m);
    127     a.resize(n, vector<int>(m));
    128     for(int i = 0; i < n; i++)
    129         for(int j = 0; j < m; j++)
    130             scanf("%d", &a[i][j]);
    131     int lf = 0;
    132     int rg = int(1e9) + 43;
    133     while(rg - lf > 1)
    134     {
    135         int m = (lf + rg) / 2;
    136         if(can(m))
    137             lf = m;
    138         else
    139             rg = m;            
    140     }
    141     assert(can(lf));
    142     printf("%d %d\n", a1 + 1, a2 + 1);
    143 }
    144 ```
    145 
    146 [1288E - Messenger Simulator](/contest/1288/problem/E "Educational Codeforces Round 80 (Rated for Div. 2)")
    147 
    148 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    149 
    150 **Tutorial**
    151 
    152 Tutorial is loading...
    153 
    154 **Solution 1 (pikmike)**
    155 
    156 ```
    157 #include <bits/stdc++.h>
    158 
    159 #define forn(i, n) for (int i = 0; i < int(n); i++)
    160 #define x first 
    161 #define y second
    162 
    163 using namespace std;
    164 
    165 const int N = 300 * 1000 + 13;
    166 const int P = 550;
    167 
    168 typedef pair<int, int> pt;
    169 
    170 int n;
    171 int a[N];
    172 vector<int> pos[N];
    173 pt ans[N];
    174 
    175 int cnt[N];
    176 int tot;
    177 
    178 void add(int x){
    179 	++cnt[x];
    180 	if (cnt[x] == 1) ++tot;
    181 }
    182 
    183 void rem(int x){
    184 	if (cnt[x] == 1) --tot;
    185 	--cnt[x];
    186 }
    187 
    188 int f[N];
    189 
    190 void upd(int x){
    191 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    192 		++f[i];
    193 }
    194 
    195 int get(int x){
    196 	int res = 0;
    197 	for (int i = x; i < N; i |= i + 1)
    198 		res += f[i];
    199 	return res;
    200 }
    201 
    202 int main() {
    203 	int n, m;
    204 	scanf("%d%d", &n, &m);
    205 	forn(i, m){
    206 		scanf("%d", &a[i]);
    207 		--a[i];
    208 	}
    209 	forn(i, m){
    210 		pos[a[i]].push_back(i);
    211 	}
    212 	
    213 	vector<pt> qr;
    214 	forn(i, n){
    215 		for (int j = 1; j < int(pos[i].size()); ++j)
    216 			qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
    217 		if (!pos[i].empty())
    218 			qr.push_back(make_pair(pos[i].back() + 1, m - 1));
    219 	}
    220 	
    221 	sort(qr.begin(), qr.end(), [](const pt &a, const pt &b){
    222 		if (a.x / P != b.x / P)
    223 			return a.x < b.x;
    224 		if ((a.x / P) & 1)
    225 			return a.y < b.y;
    226 		return a.y > b.y;
    227 	});
    228 	
    229 	forn(i, n) ans[i] = {i, i};
    230 	forn(i, m) ans[a[i]].x = 0;
    231 	
    232 	int L = 0, R = -1;
    233 	forn(i, qr.size()){
    234 		int l = qr[i].x;
    235 		int r = qr[i].y;
    236 		if (r < l) continue;
    237 		
    238 		int x = a[qr[i].x - 1];
    239 		while (L < l) rem(a[L++]);
    240 		while (L > l) add(a[--L]);
    241 		while (R > r) rem(a[R--]);
    242 		while (R < r) add(a[++R]);
    243 		
    244 		ans[x].y = max(ans[x].y, tot);
    245 	}
    246 	forn(i, m){
    247 		if (i == pos[a[i]][0]){
    248 			ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
    249 			upd(a[i]);
    250 		}
    251 	}
    252 	forn(i, n) if (pos[i].empty()){
    253 		ans[i].y = max(ans[i].y, i + get(i));
    254 	}
    255 	
    256 	forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
    257 	return 0;
    258 }
    259 ```
    260 
    261 **Solution 2 (pikmike)**
    262 
    263 ```
    264 #include <bits/stdc++.h>
    265 
    266 #define forn(i, n) for (int i = 0; i < int(n); i++)
    267 #define x first 
    268 #define y second
    269 
    270 using namespace std;
    271 
    272 const int N = 300 * 1000 + 13;
    273 
    274 typedef pair<int, int> pt;
    275 
    276 int n;
    277 int a[N];
    278 vector<int> pos[N];
    279 pt ans[N];
    280 int prv[N];
    281 
    282 vector<int> t[4 * N];
    283 
    284 void build(int v, int l, int r){
    285 	if (l == r - 1){
    286 		t[v].push_back(prv[l]);
    287 		return;
    288 	}
    289 	int m = (l + r) / 2;
    290 	build(v * 2, l, m);
    291 	build(v * 2 + 1, m, r);
    292 	t[v].resize(r - l);
    293 	merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin());
    294 }
    295 
    296 int get(int v, int l, int r, int L, int R, int val){
    297 	if (L >= R)
    298 		return 0;
    299 	if (l == L && r == R)
    300 		return lower_bound(t[v].begin(), t[v].end(), val) - t[v].begin();
    301 	int m = (l + r) / 2;
    302 	return get(v * 2, l, m, L, min(m, R), val) + get(v * 2 + 1, m, r, max(m, L), R, val);
    303 }
    304 
    305 int f[N];
    306 
    307 void upd(int x){
    308 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    309 		++f[i];
    310 }
    311 
    312 int get(int x){
    313 	int res = 0;
    314 	for (int i = x; i < N; i |= i + 1)
    315 		res += f[i];
    316 	return res;
    317 }
    318 
    319 int main() {
    320 	int n, m;
    321 	scanf("%d%d", &n, &m);
    322 	forn(i, m){
    323 		scanf("%d", &a[i]);
    324 		--a[i];
    325 	}
    326 	forn(i, m){
    327 		pos[a[i]].push_back(i);
    328 	}
    329 	
    330 	vector<pt> qr;
    331 	forn(i, n){
    332 		for (int j = 1; j < int(pos[i].size()); ++j)
    333 			qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
    334 		if (!pos[i].empty())
    335 			qr.push_back(make_pair(pos[i].back() + 1, m - 1));
    336 	}
    337 	
    338 	forn(i, n) ans[i] = {i, i};
    339 	forn(i, m) ans[a[i]].x = 0;
    340 	
    341 	forn(i, n){
    342 		int cur = -1;
    343 		for (auto it : pos[i]){
    344 			prv[it] = cur;
    345 			cur = it;
    346 		}
    347 	}
    348 	build(1, 0, m);
    349 	
    350 	forn(i, qr.size()){
    351 		int l = qr[i].x;
    352 		int r = qr[i].y;
    353 		if (r < l) continue;
    354 		int x = a[qr[i].x - 1];
    355 		int cnt = get(1, 0, m, l, r + 1, l);
    356 		ans[x].y = max(ans[x].y, cnt);
    357 	}
    358 	
    359 	forn(i, m){
    360 		if (i == pos[a[i]][0]){
    361 			ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
    362 			upd(a[i]);
    363 		}
    364 	}
    365 	forn(i, n) if (pos[i].empty()){
    366 		ans[i].y = max(ans[i].y, i + get(i));
    367 	}
    368 	
    369 	forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
    370 	return 0;
    371 }
    372 ```
    373 
    374 **Solution 3 (pikmike)**
    375 
    376 ```
    377 #include <bits/stdc++.h>
    378 
    379 #define forn(i, n) for (int i = 0; i < int(n); i++)
    380 
    381 using namespace std;
    382 
    383 const int N = 600 * 1000 + 13;
    384 
    385 int f[N];
    386 
    387 void upd(int x, int val){
    388 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    389 		f[i] += val;
    390 }
    391 
    392 int get(int x){
    393 	int res = 0;
    394 	for (int i = x; i < N; i |= i + 1)
    395 		res += f[i];
    396 	return res;
    397 }
    398 
    399 int main() {
    400 	int n, m;
    401 	scanf("%d%d", &n, &m);
    402 	vector<int> mn(n);
    403 	iota(mn.begin(), mn.end(), 0);
    404 	vector<int> mx = mn;
    405 	
    406 	vector<int> a(m);
    407 	forn(i, m){
    408 		scanf("%d", &a[i]);
    409 		--a[i];
    410 		mn[a[i]] = 0;
    411 	}
    412 	
    413 	vector<int> pos(n);
    414 	forn(i, n) pos[i] = n - i - 1;
    415 	forn(i, n) upd(i, 1);
    416 	
    417 	forn(i, m){
    418 		mx[a[i]] = max(mx[a[i]], get(pos[a[i]] + 1));
    419 		upd(pos[a[i]], -1);
    420 		pos[a[i]] = i + n;
    421 		upd(pos[a[i]], 1);
    422 	}
    423 	forn(i, n){
    424 		mx[i] = max(mx[i], get(pos[i] + 1));
    425 	}
    426 	
    427 	forn(i, n) printf("%d %d\n", mn[i] + 1, mx[i] + 1);
    428 	return 0;
    429 }
    430 ```
    431 
    432 [1288F - Red-Blue Graph](/contest/1288/problem/F "Educational Codeforces Round 80 (Rated for Div. 2)")
    433 
    434 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    435 
    436 **Tutorial**
    437 
    438 Tutorial is loading...
    439 
    440 **Solution (BledDest)**
    441 
    442 ```
    443 #include<bits/stdc++.h>
    444 
    445 using namespace std;
    446 
    447 const int N = 443;
    448 
    449 int n1, n2, m, r, b;
    450 string s1, s2;
    451 int u[N];
    452 int v[N];
    453 
    454 struct edge
    455 {
    456     int y, c, f, cost;
    457     edge() {};
    458     edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
    459 };
    460 
    461 int bal[N][N];
    462 int s, t, oldS, oldT, V;
    463 vector<int> g[N];
    464 vector<edge> e;
    465 
    466 void add(int x, int y, int c, int cost)
    467 {
    468     g[x].push_back(e.size());
    469     e.push_back(edge(y, c, 0, cost));
    470     g[y].push_back(e.size());
    471     e.push_back(edge(x, 0, 0, -cost));
    472 }
    473 
    474 int rem(int num)
    475 {
    476     return e[num].c - e[num].f;
    477 }   
    478 
    479 void add_LR(int x, int y, int l, int r, int cost)
    480 {
    481     int c = r - l;
    482     if(l > 0)
    483     {
    484         add(s, y, l, cost);
    485         add(x, t, l, cost);
    486     }
    487     if(c > 0)
    488     {
    489         add(x, y, c, cost);
    490     }
    491 }
    492 
    493 int p[N];
    494 int d[N];
    495 int pe[N];
    496 int inq[N];
    497 
    498 bool enlarge()
    499 {
    500     for(int i = 0; i < V; i++)
    501     {
    502         d[i] = int(1e9);
    503         p[i] = -1;
    504         pe[i] = -1;
    505         inq[i] = 0;
    506     }
    507     d[s] = 0;
    508     queue<int> q;
    509     q.push(s);
    510     inq[s] = 1;
    511     while(!q.empty())
    512     {
    513         int k = q.front();
    514         q.pop();
    515         inq[k] = 0;
    516         for(auto z : g[k])
    517         {
    518             if(!rem(z)) continue;
    519             if(d[e[z].y] > d[k] + e[z].cost)
    520             {
    521                 p[e[z].y] = k;
    522                 pe[e[z].y] = z;
    523                 d[e[z].y] = d[k] + e[z].cost;
    524                 if(!inq[e[z].y])
    525                 {
    526                     q.push(e[z].y);
    527                     inq[e[z].y] = 1;
    528                 }
    529             }
    530         }
    531     }
    532     if(p[t] == -1)
    533         return false;
    534     int cur = t;
    535     while(cur != s)
    536     {
    537         e[pe[cur]].f++;
    538         e[pe[cur] ^ 1].f--;
    539         cur = p[cur];
    540     }
    541     return true;
    542 }
    543 
    544 void add_edge(int x, int y)
    545 {
    546     add(x, y + n1, 1, r);
    547     add(y + n1, x, 1, b);
    548 }
    549 
    550 void impose_left(int x)
    551 {
    552     if(s1[x] == 'R')
    553     {
    554         add_LR(oldS, x, 1, m, 0);
    555     }
    556     else if(s1[x] == 'B')
    557     {
    558         add_LR(x, oldT, 1, m, 0);
    559     }
    560     else
    561     {
    562         add(oldS, x, m, 0);
    563         add(x, oldT, m, 0);
    564     }
    565 }
    566 
    567 void impose_right(int x)
    568 {
    569     if(s2[x] == 'R')
    570     {
    571         add_LR(x + n1, oldT, 1, m, 0);
    572     }
    573     else if(s2[x] == 'B')
    574     {
    575         add_LR(oldS, x + n1, 1, m, 0);
    576     }
    577     else
    578     {
    579         add(oldS, x + n1, m, 0);
    580         add(x + n1, oldT, m, 0);
    581     }
    582 }
    583 
    584 void construct_bal()
    585 {
    586     for(int i = 0; i < n1; i++)
    587     {
    588         for(auto z : g[i])
    589         {
    590             if(e[z].y >= n1 && e[z].y < n1 + n2)
    591                 bal[i][e[z].y - n1] += e[z].f;
    592         }
    593     }
    594 }
    595 
    596 void find_ans()
    597 {
    598     int res = 0;
    599     string w = "";
    600     for(auto x : g[s])
    601         if(rem(x))
    602         {
    603             cout << -1 << endl;
    604             return;
    605         }
    606     for(int i = 0; i < m; i++)
    607     {
    608         if(bal[u[i]][v[i]] > 0)
    609         {
    610             bal[u[i]][v[i]]--;
    611             res += r;
    612             w += "R";
    613         }
    614         else if(bal[u[i]][v[i]] < 0)
    615         {
    616             bal[u[i]][v[i]]++;
    617             res += b;
    618             w += "B";
    619         }
    620         else w += "U";
    621     }
    622     cout << res << endl << w << endl;
    623 }
    624 
    625 int main()
    626 {                       
    627     cin >> n1 >> n2 >> m >> r >> b;
    628     cin >> s1;
    629     cin >> s2;
    630     for(int i = 0; i < m; i++)
    631     {
    632         cin >> u[i] >> v[i];
    633         u[i]--;
    634         v[i]--;
    635     }
    636 
    637     oldS = n1 + n2;
    638     oldT = oldS + 1;
    639     s = oldT + 1;
    640     t = s + 1;
    641     V = t + 1;
    642 
    643     for(int i = 0; i < n1; i++)
    644         impose_left(i);
    645     for(int i = 0; i < n2; i++)
    646         impose_right(i);
    647     for(int i = 0; i < m; i++)
    648         add_edge(u[i], v[i]);
    649     add(oldT, oldS, 100000, 0);
    650     while(enlarge());
    651     construct_bal();
    652     find_ans();
    653 }
    654 ```