codeforces-scrape

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

1167.md (8734B)


      1 Source: https://codeforces.com/blog/entry/67058
      2 
      3 [1167A - Telephone Number](/contest/1167/problem/A "Educational Codeforces Round 65 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int n;
     19 string s;
     20 
     21 int main(){
     22     int tc;
     23     cin >> tc;
     24     for(int t = 0; t < tc; ++t){
     25         cin >> n >> s;
     26         int pos = n;
     27         for(int i = 0; i < n; ++i)
     28             if(s[i] == '8'){
     29                 pos = i;
     30                 break;
     31             }
     32             
     33         if(n - pos >= 11)
     34             cout << "YES\n";
     35         else
     36             cout << "NO\n";
     37     }
     38 	return 0;
     39 }
     40 ```
     41 
     42 [1167B - Lost Numbers](/contest/1167/problem/B "Educational Codeforces Round 65 (Rated for Div. 2)")
     43 
     44 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution (BledDest)**
     51 
     52 ```
     53 #include<bits/stdc++.h>
     54 
     55 using namespace std;
     56 
     57 vector<int> p = {4, 8, 15, 16, 23, 42};
     58 int ans[4];
     59 
     60 int main()
     61 {
     62 	for(int i = 0; i < 4; i++)
     63 	{
     64 		cout << "? " << i + 1 << " " << i + 2 << endl;
     65 		cout.flush();
     66 		cin >> ans[i];
     67 	}
     68 	do
     69 	{
     70 		bool good = true;
     71 		for(int i = 0; i < 4; i++)
     72 			good &= (p[i] * p[i + 1] == ans[i]);
     73 		if(good) break;
     74 	}
     75 	while(next_permutation(p.begin(), p.end()));
     76 	cout << "!";
     77 	for(int i = 0; i < 6; i++)
     78 		cout << " " << p[i];
     79 	cout << endl;
     80 	cout.flush();
     81 	return 0;
     82 }
     83 ```
     84 
     85 [1167C - News Distribution](/contest/1167/problem/C "Educational Codeforces Round 65 (Rated for Div. 2)")
     86 
     87 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (BledDest)**
     94 
     95 ```
     96 #include<bits/stdc++.h>
     97 using namespace std;
     98 
     99 const int N = 1000043;
    100 vector<int> g[N];
    101 
    102 int color[N];
    103 int siz[N];
    104 int n, m;
    105 int cc = 0;
    106 
    107 int dfs(int x)
    108 {
    109 	if(color[x])
    110 		return 0;
    111 	color[x] = cc;
    112 	int ans = (x < n ? 1 : 0);
    113 	for(auto y : g[x])
    114 		ans += dfs(y);
    115 	return ans; 
    116 }
    117 
    118 int main()
    119 {
    120 	scanf("%d %d", &n, &m);
    121 	for(int i = 0; i < m; i++)
    122 	{
    123 		int k;
    124 		scanf("%d", &k);
    125 		for(int j = 0; j < k; j++)
    126 		{
    127 			int x;
    128 			scanf("%d", &x);
    129 			--x;
    130 			g[x].push_back(i + n);
    131 			g[i + n].push_back(x);
    132 		}
    133 	}
    134 	for(int i = 0; i < n; i++)
    135 	{
    136 		if(!color[i])
    137 		{
    138 			cc++;
    139 			siz[cc] = dfs(i);
    140 		}
    141 		printf("%d ", siz[color[i]]);
    142 	}
    143 }
    144 ```
    145 
    146 **Solution (PikMike)**
    147 
    148 ```
    149 #include <bits/stdc++.h>
    150 
    151 using namespace std;
    152 
    153 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    154 
    155 const int N = 500 * 1000 + 13;
    156 
    157 int n, m;
    158 int rk[N], p[N];
    159 
    160 int getP(int a){
    161 	return (a == p[a] ? a : p[a] = getP(p[a]));
    162 }
    163 
    164 void unite(int a, int b){
    165 	a = getP(a), b = getP(b);
    166 	if (a == b) return;
    167 	if (rk[a] < rk[b]) swap(a, b);
    168 	p[b] = a;
    169 	rk[a] += rk[b];
    170 }
    171 
    172 int main(){
    173 	scanf("%d%d", &n, &m);
    174 	forn(i, n) p[i] = i, rk[i] = 1;
    175 	
    176 	forn(i, m){
    177 		int k;
    178 		scanf("%d", &k);
    179 		int lst = -1;
    180 		forn(j, k){
    181 			int x;
    182 			scanf("%d", &x);
    183 			--x;
    184 			if (lst != -1)
    185 				unite(x, lst);
    186 			lst = x;
    187 		}
    188 	}
    189 	
    190 	forn(i, n)
    191 		printf("%d ", rk[getP(i)]);
    192 	puts("");
    193 }
    194 ```
    195 
    196 [1167D - Bicolored RBS](/contest/1167/problem/D "Educational Codeforces Round 65 (Rated for Div. 2)")
    197 
    198 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    199 
    200 **Tutorial**
    201 
    202 Tutorial is loading...
    203 
    204 **Solution (adedalic)**
    205 
    206 ```
    207 #include<bits/stdc++.h>
    208 using namespace std;
    209 
    210 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    211 #define sz(a) int((a).size())
    212 
    213 int n;
    214 string s;
    215 
    216 inline bool read() {
    217 	if(!(cin >> n))
    218 		return false;
    219 	cin >> s;
    220 	return true;
    221 }
    222 
    223 inline void solve() {
    224 	string t(n, '0');
    225 	
    226 	int bal = 0;
    227 	fore(i, 0, n) {
    228 		if(s[i] == ')')
    229 			bal--;
    230 		
    231 		t[i] = char('0' + (bal & 1));
    232 		
    233 		if(s[i] == '(')
    234 			bal++;
    235 	}
    236 	
    237 	cout << t << endl;
    238 }
    239 
    240 int main() {
    241 #ifdef _DEBUG
    242 	freopen("input.txt", "r", stdin);
    243 	int tt = clock();
    244 #endif
    245 	
    246 	if(read()) {
    247 		solve();
    248 		
    249 #ifdef _DEBUG
    250 		cerr << "TIME = " << clock() - tt << endl;
    251 		tt = clock();
    252 #endif
    253 	}
    254 	return 0;
    255 }
    256 ```
    257 
    258 [1167E - Range Deleting](/contest/1167/problem/E "Educational Codeforces Round 65 (Rated for Div. 2)")
    259 
    260 Idea: [Roms](/profile/Roms "Master Roms")
    261 
    262 **Tutorial**
    263 
    264 Tutorial is loading...
    265 
    266 **Solution (Roms)**
    267 
    268 ```
    269 #include <bits/stdc++.h>
    270 
    271 using namespace std;
    272 
    273 const int N = int(1e6) + 99;
    274 int n, x;
    275 int a[N];
    276 vector <int> pos[N];
    277 int prefMax[N];
    278 
    279 int main() {
    280 	scanf("%d %d", &n, &x);
    281 	for(int i = 0; i < n; ++i){
    282 		scanf("%d", a + i);
    283 		pos[a[i]].push_back(i);	
    284 		prefMax[i] = max(a[i], (i > 0 ? prefMax[i - 1] : a[i]));
    285 	}
    286 	
    287 	int p = 1;
    288 	int lst = n + 5;
    289 	for(int i = x; i >= 1; --i){
    290 		if(pos[i].empty()){
    291 		    p = i;
    292 		    continue;
    293 		}
    294 		if(pos[i].back() > lst) break;
    295 		p = i;
    296 		lst = pos[i][0];
    297 	}	
    298 
    299 	long long res = 0;
    300 	lst = -1;
    301 	for(int l = 1; l <= x; ++l){
    302 		int r = max(l, p - 1);
    303 		if(lst != -1) r = max(r, prefMax[lst]);
    304 		res += x - r + 1;
    305 		if(!pos[l].empty()){
    306     		if(pos[l][0] < lst) break;
    307     		lst = pos[l].back();
    308 		}
    309 	}	
    310 
    311 	cout << res << endl;
    312 	return 0;
    313 }
    314 ```
    315 
    316 [1167F - Scalar Queries](/contest/1167/problem/F "Educational Codeforces Round 65 (Rated for Div. 2)")
    317 
    318 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    319 
    320 **Tutorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Solution (adedalic)**
    325 
    326 ```
    327 #include<bits/stdc++.h>
    328 using namespace std;
    329 
    330 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    331 #define sz(a) int((a).size())
    332 
    333 typedef long long li;
    334 
    335 const int MOD = int(1e9) + 7;
    336 
    337 int add(int a, int b) {
    338 	a += b;
    339 	while(a >= MOD)
    340 		a -= MOD;
    341 	while(a < 0)
    342 		a += MOD;
    343 	return a;
    344 }
    345 int mul(int a, int b) {
    346 	return int(a * 1ll * b % MOD);
    347 }
    348 
    349 int n;
    350 vector<int> a;
    351 
    352 inline bool read() {
    353 	if(!(cin >> n))
    354 		return false;
    355 	a.resize(n);
    356 	fore(i, 0, n)
    357 		cin >> a[i];
    358 	return true;
    359 }
    360 
    361 vector<li> f;
    362 void inc(int pos, int val) {
    363 	for(; pos < sz(f); pos |= pos + 1)
    364 		f[pos] += val;
    365 }
    366 li sum(int pos) {
    367 	li ans = 0;
    368 	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
    369 		ans += f[pos];
    370 	return ans;
    371 }
    372 
    373 vector<int> S[2];
    374 
    375 inline void solve() {
    376 	fore(k, 0, 2) {
    377 		S[k].assign(n, 0);
    378 		f.assign(n, 0);
    379 		
    380 		vector<int> dx(a.begin(), a.end());
    381 		sort(dx.begin(), dx.end());
    382 		
    383 		fore(i, 0, n) {
    384 			int pos = int(lower_bound(dx.begin(), dx.end(), a[i]) - dx.begin());
    385 			S[k][i] = int(sum(pos) % MOD);
    386 			inc(pos, i + 1);
    387 		}
    388 		reverse(a.begin(), a.end());
    389 	}
    390 	
    391 	reverse(S[1].begin(), S[1].end());
    392 	int ans = 0;
    393 	fore(i, 0, n) 
    394 		ans = add(ans, mul(a[i], add(mul(i + 1, n - i), add(mul(S[0][i], n - i), mul(S[1][i], i + 1)))));
    395 	
    396 	cout << ans << endl;
    397 }
    398 
    399 int main() {
    400 #ifdef _DEBUG
    401 	freopen("input.txt", "r", stdin);
    402 	int tt = clock();
    403 #endif
    404 	ios_base::sync_with_stdio(false);
    405 	cin.tie(0), cout.tie(0);
    406 	
    407 	if(read()) {
    408 		solve();
    409 		
    410 #ifdef _DEBUG
    411 		cerr << "TIME = " << clock() - tt << endl;
    412 		tt = clock();
    413 #endif
    414 	}
    415 	return 0;
    416 }
    417 ```
    418 
    419 [1167G - Low Budget Inception](/contest/1167/problem/G "Educational Codeforces Round 65 (Rated for Div. 2)")
    420 
    421 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    422 
    423 **Tutorial**
    424 
    425 Tutorial is loading...
    426 
    427 **Solution (adedalic)**
    428 
    429 ```
    430 #include<bits/stdc++.h>
    431 
    432 using namespace std;
    433 
    434 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    435 #define sz(a) int((a).size())
    436 
    437 #define x first
    438 #define y second
    439 
    440 typedef long long li;
    441 
    442 const int INF = int(1e9);
    443 const li INF64 = li(1e18);
    444 
    445 const int N = 200 * 1000 + 555;
    446 const int D = 7077;
    447 
    448 int n, d, m;
    449 int a[N], qs[N];
    450 
    451 inline bool read() {
    452 	if(scanf("%d%d", &n, &d) != 2)
    453 		return false;
    454 	fore(i, 0, n)
    455 		scanf("%d", &a[i]);
    456 	
    457 	assert(scanf("%d", &m) == 1);
    458 	fore(i, 0, m)
    459 		scanf("%d", &qs[i]);
    460 	return true;
    461 }
    462 
    463 bitset<D> L, R, cur;
    464 int dist[N];
    465 set<int> has;
    466 
    467 void shiftL(int s, int t, int &uk) {
    468 	L <<= t - s;
    469 	for(; uk < n && a[uk] < t; uk++) {
    470 		if(t - a[uk] - 1 < D)
    471 			L[t - a[uk] - 1] = 1;
    472 		if(t - a[uk] < D)
    473 			L[t - a[uk]] = 1;
    474 	}
    475 }
    476 
    477 void shiftR(int s, int t, int &uk) {
    478 	R >>= t - s;
    479 	if(!has.count(t))
    480 		R[0] = 0;
    481 	
    482 	for(; uk < n && a[uk] < t + D; uk++) {
    483 		if(a[uk] - t >= 0) {
    484 			R[a[uk] - t] = 1;
    485 			if(a[uk] - t + 1 >= 0)
    486 				R[a[uk] - t + 1] = 1;
    487 		}
    488 	}
    489 }
    490 
    491 inline void solve() {
    492 	fore(i, 0, m) {
    493 		dist[i] = INF;
    494 		int pos = int(lower_bound(a, a + n, qs[i]) - a);
    495 		if(pos > 0)
    496 			dist[i] = qs[i] - a[pos - 1] - 1;
    497 		if(pos < n)
    498 			dist[i] = min(dist[i], a[pos] - qs[i]);
    499 	}
    500 	has = set<int>(a, a + n);
    501 	
    502 	int uL = 0, uR = 0;
    503 	L.reset();
    504 	R.reset();
    505 	fore(i, 0, m) {
    506 		shiftL(i > 0 ? qs[i - 1] : -D, qs[i], uL);
    507 		shiftR(i > 0 ? qs[i - 1] : -D, qs[i], uR);
    508 		
    509 		double ans = atan2(1, dist[i]);
    510 
    511 		cur = L & R;
    512 		int pos = (int)cur._Find_first();
    513 		if(pos < D) {
    514 			int ds = pos;
    515 			ans = max(ans, 2 * atan2(1, ds));
    516 		}
    517 		printf("%.15f\n", ans);
    518 	}
    519 }
    520 
    521 int main() {
    522 #ifdef _DEBUG
    523 	freopen("input.txt", "r", stdin);
    524 	int tt = clock();
    525 #endif
    526 	cout << fixed << setprecision(15);
    527 	
    528 	if(read()) {
    529 		solve();
    530 		
    531 #ifdef _DEBUG
    532 		cerr << "TIME = " << clock() - tt << endl;
    533 		tt = clock();
    534 #endif
    535 	}
    536 	return 0;
    537 }
    538 ```